Algorithms

Moderators: None (Apply to moderate this forum)
Number of posts: 786

This Forum Only

Permutation Algorithm help Posted by da_comp_guy on 21 Feb 2008 at 9:22 PM
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 ...

"The GEEK Shall Inherit The Earth"
Re: Permutation Algorithm help Posted by zibadian on 21 Feb 2008 at 10:37 PM
: 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 ...
:
: "The GEEK Shall Inherit The Earth"

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

if (length permutation < required length) {
for (i = min digit to max digit) {
if (i not in permutation) {
makePermutations(permutation+i)
}
}
} else {
}
}
```
Re: Permutation Algorithm help Posted by da_comp_guy on 22 Feb 2008 at 4:26 AM
can u plz elaborate a bit more..
"The GEEK Shall Inherit The Earth"
Re: Permutation Algorithm help Posted by zibadian on 22 Feb 2008 at 11:02 AM
: can u plz elaborate a bit more..
: "The GEEK Shall Inherit The Earth"

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:
```  for (each digit) {
show digit
}
```

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:
```  for (first: each digit) {
for (second: each digit) {
if (second <> first)
show first+second
}
}
```

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.
Re: Permutation Algorithm help Posted by swapson on 5 Sept 2010 at 9:09 AM
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<Long> lstOfPermuted;
private Long input;
private int mainPointer;
private String tempInput;
int pointer;;
public Permutation(Long input) {
lstOfPermuted=new ArrayList();
this.input=input;
}
public List<Long> 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))))
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))))

}
private String rotate(char data[],int pointer){
char firstElem=data[pointer];
int counter=pointer;
for(int i=pointer+1;i<data.length;i++){
data[counter]=data[i];
counter++;
}
data[data.length-1]=firstElem;
return new String(data);
}
public Long getInput() {
return input;
}

public static void main(String args[]){
Long data=123L;
IPermutation perm= new Permutation(data);
List<Long> permutedData=perm.permutate();
System.out.println(permutedData.toString()+"-"+permutedData.size());
}

}

This program will not include duplicates value inside the permutated data.
Re: Permutation Algorithm help Posted by smithjackson on 2 Oct 2010 at 2:06 PM

Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic