Permutation Algorithm help

I need to find all possible distinct permutations of the digits a given number.
eg:
1234
2134
2143 ... n so on.

can any please tell me how do i proceed ? i have devised an algorithm myself, which swaps consecutive numbers... but it works only for 3 digit numbers. but the above mentioned problem needs to work for all numbers.
plzzz help ...

"[b]The[blue] GEEK[/blue] Shall Inherit The Earth" ;-) [/b]

Comments

  • : I need to find all possible distinct permutations of the digits a
    : given number.
    : eg:
    : 1234
    : 2134
    : 2143 ... n so on.
    :
    : can any please tell me how do i proceed ? i have devised an
    : algorithm myself, which swaps consecutive numbers... but it works
    : only for 3 digit numbers. but the above mentioned problem needs to
    : work for all numbers.
    : plzzz help ...
    :
    : "[b]The[blue] GEEK[/blue] Shall Inherit The Earth" ;-) [/b]

    Here's in pseudo code a general permutation algorithm. It can create permutations of any length with any number of digits:
    [code]
    makePermutations(permutation) {

    if (length permutation < required length) {
    for (i = min digit to max digit) {
    if (i not in permutation) {
    makePermutations(permutation+i)
    }
    }
    } else {
    add permutation to list
    }
    }
    [/code]
  • can u plz elaborate a bit more..
    "[b]The[blue] GEEK[/blue] Shall Inherit The Earth" ;-) [/b]
  • : can u plz elaborate a bit more..
    : "[b]The[blue] GEEK[/blue] Shall Inherit The Earth" ;-) [/b]

    The algorithm is quite basic. If you want to know all the permutations of a 1 digit number, then you simply loop across that digit:
    [code]
    for (each digit) {
    show digit
    }
    [/code]
    If you want to find the permutations of two digits, you loop across the first and for every step in that loop you loop across the second digit if it is not equal to the first:
    [code]
    for (first: each digit) {
    for (second: each digit) {
    if (second <> first)
    show first+second
    }
    }
    [/code]
    This process repeats itself for every additional digit in the permutation. You could create a nested loop as deep as you like, but if you want to add another, then you need to change the code.
    Luckily for programmers it is possible to call a procedure from itself (recursive procedures). This allows you to dynamically nest loops one in the other. The pseudo code I gave earlier is a recursive solution for permutations.
  • import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.Stack;

    public class Permutation implements IPermutation{
    private List lstOfPermuted;
    private Long input;
    private int mainPointer;
    private String tempInput;
    int pointer;;
    public Permutation(Long input) {
    lstOfPermuted=new ArrayList();
    this.input=input;
    }
    public List permutate(){
    tempInput=input.toString();
    mainPointer=tempInput.length();
    pointer=mainPointer;
    permutate(tempInput.toCharArray(),0,mainPointer);
    return lstOfPermuted;
    }

    private void permutate(char data[],int counter,int mainPtr){
    String permuteData=null;
    String strData=new String(data);
    if(!lstOfPermuted.contains(Long.parseLong(new String(strData))))
    lstOfPermuted.add(Long.parseLong(strData));
    pointer--;
    if(pointer>0){
    if(data.length==mainPointer){
    permuteData=rotate(data,counter);
    permutate(permuteData.toCharArray(),counter,mainPtr);
    mainPointer=tempInput.length();
    }else{
    permuteData=rotate(data,counter);
    permutate(permuteData.toCharArray(),counter,mainPtr);
    mainPointer=mainPtr;
    }
    }

    if(mainPointer>3){
    pointer=--mainPointer;
    permutate(strData.toCharArray(),++counter,mainPointer);
    }
    char dataTemp[]=strData.toCharArray();
    char temp=dataTemp[dataTemp.length-1];
    dataTemp[dataTemp.length-1]=dataTemp[dataTemp.length-2];
    dataTemp[dataTemp.length-2]=temp;
    if(!lstOfPermuted.contains(Long.parseLong(new String(dataTemp))))
    lstOfPermuted.add(Long.parseLong(new String(dataTemp)));

    }
    private String rotate(char data[],int pointer){
    char firstElem=data[pointer];
    int counter=pointer;
    for(int i=pointer+1;i permutedData=perm.permutate();
    System.out.println(permutedData.toString()+"-"+permutedData.size());
    }

    }


    This program will not include duplicates value inside the permutated data.
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories