Permutation Algorithm help - Programmers Heaven

Howdy, Stranger!

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

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Permutation Algorithm help

da_comp_guyda_comp_guy Posts: 37Member
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

  • zibadianzibadian Posts: 6,349Member
    : 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]
  • da_comp_guyda_comp_guy Posts: 37Member
    can u plz elaborate a bit more..
    "[b]The[blue] GEEK[/blue] Shall Inherit The Earth" ;-) [/b]
  • zibadianzibadian Posts: 6,349Member
    : 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.
  • swapsonswapson Posts: 1Member
    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.