How do I find all possible positions?
If I have 3 positions and 3 numbers I know there are 6 possible soultions (of having a diff number in each)
If I have 4 positions and 4 numbers I know there are 12 possible soultions (of having a diff number in each)
I know the function to find the number of diff positions in n! where n is the number of positions ( + is the ! called shreek?)
5! = 5 * 4 * 3 * 2 * 1 = 120 diff positions
But how do I find out what all the different positions are (ie to print out a list)
I just can't work out how to write an algorithm for this.
Maybe there is somwwhere on the web I can find out, but Google won't let me search for ! + I don't know the real name for it.
It's called factorialSee: http://en.wikipedia.org/wiki/Factorial
> + is the ! called shreek?)In uinx it is called a 'bang' .
> It's called factorial> See: http://en.wikipedia.org/wiki/FactorialThanksBut what I'm really after is some help or pointers in writing an algorithm that will print out all the 120 solutions for Factorial 5
> > It's called factorial
> > See: http://en.wikipedia.org/wiki/Factorial
>
> Thanks
>
> But what I'm really after is some help or pointers in
> writing an algorithm that will print out all the 120
> solutions for Factorial 5
Fill an array with your 5 numbers and then pair wise swap elements in a systematic manner. There is a nice recursive approach to the swapping by noting that an n th order version can be processes an n times an (n-1) the order version.
For some of the more than 30 available algorithms check out:
http://www.princeton.edu/~rblee/ELE572Papers/p137-sedgewick.pdf
Here is one of them (short code - obtuse reasoning), due to Langdon, translated into Java.
/* Generate all permutation of n elements
from Knuth Art of Computer Programming Vol 4 p56 Algorithm C
due to G. G. Langdon, Jr. [CACM 10 (1967) 298-299]
one of the shorter permutation algorithms though not the most efficient.
--
efficiency is probably not much of a consideration. Since the
output grows by n! you will never use this or any other algorithm
with any n much bigger than 10 anyway.
*/
public static void printPermutation(int n){
int[] a = new int[n+1];
for(int i = 1; i<=n; i++){a[i]=i;}
int k=n;
while(k>1){
for(int i = 1; i<=n; i++){System.out.print(a[i]);};System.out.println();//spew
k=n;
while(true){
//shift
int temp = a[1];
for(int i=1; i<k; i++){a[i]=a[i+1];}
a[k] = temp;
if(k==1 || a[k] != k) break;
k--;
}
}
}
>
... here's another one: it produces permutations in a lexicographical
order. (pseudo code):
1) let p_0, p_1, ... p_n be a permutation;
2) let i be the largest value such that p_i < p_i+1;
3) if no such i can be found, the current permutation was the last one: stop;
4) let j be the largest value such that p_j > p_i;
5) swap p_i and p_j;
6) reverse p_i+1 ... p_n;
7) go to step 2.
Here's a small example: let the current permucation be abedc.
i == 1, because b < e. j == 4, because c > b.
swap p_1 and p_4: acedb. reverse p_2 ... p_4; result is: acbde.
IOW acbde is lexicographically the next permutation of abedc.
Note that this little algorithm also works when duplicate elements are
present in the permutation.
kind regards,
Jos
JosAHa at 2007-7-16 23:13:01 >
So tell me jos - I was looking at a Forth forum the other day. I used to work in Forth about 20 years ago and haven't kept in touch at all. Haven't looked at anything Forth related in years. An old friend reminded me of that old obsession of mine and sent me a pointer to the forum. While reading I spotted an entry from a fellow named Jos and wondered if by any chance it was you.
Could it be that the same fellow that can rattle off lyrics to old zappa tunes as deftly as old linpac algorithms is also conversant in Forth?
: Just ( - ) curious ;
> So tell me jos - I was looking at a Forth forum the other day. I used to
> work in Forth about 20 years ago and haven't kept in touch at all.
> Haven't looked at anything Forth related in years. An old friend
> reminded me of that old obsession of mine and sent me a pointer to
> the forum. While reading I spotted an entry from a fellow named Jos
> and wondered if by any chance it was you.
>
> Could it be that the same fellow that can rattle off lyrics to old zappa
> tunes as deftly as old linpac algorithms is also conversant in Forth?
No, that wasn't me; both you and I share a similar history: I played with
Forh quite a bit in the late '70s, but I haven't done anything with it for
years. I did build an experimental CAS using RPN though lately and
quite some Forth is shining through ;-)
> : Just ( - ) curious ;
: regards kind ;
Jos
JosAHa at 2007-7-16 23:13:01 >
Fantastic.very useful.though I see that this array ignores position 0
I dashed this off. I can't read the one posted above without my eyes bleeding. This one uses recursion.
import java.util.*;
public class Test
{
public static void main(String[] args)
{
for (int[] array : permutations(5)) print(array);
}
static void print(int[] array)
{
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
System.out.print(' ');
}
System.out.println();
}
static List<int[]> permutations(int number)
{
int[] input = new int[number];
for (int i = 1; i <= number; i++) input[i - 1] = i;
return permutations(input, 0);
}
static List<int[]> permutations(int[] input, int from)
{
List<int[]> bigPerm = new ArrayList<int[]>();
for (int i = from; i < input.length; i++) {
int[] next = new int[input.length];
System.arraycopy(input, 0, next, 0, from);
next[from] = input[i];
for (int j = from + 1; j < input.length; j++) {
next[j] = input[(j <= i) ? j - 1 : j];
}
if (from < input.length - 1) {
bigPerm.addAll(permutations(next, from + 1));
} else {
bigPerm.add(next);
}
}
return bigPerm;
}
}
