Hi, i have an array of n elements and would like to find a way of finding each possible order. n could be in the reagen of 9 to 576. the number of possible permutations of 576 elements is mega and there is no way i can store that many results. what i want to do is examin each set for special properties 1 at a time.
is there a way of computing the set[idx+1] by knowing the order of set[idx]. i cannot use an indexing varialbe because for a high n value idx could become higher than the maximum a long variable can hold. i also would like to be able to start from any set so that that i can split computation between computers/GPUs/CPUs, the elements are all integers 1 to n and all values of n are square numbers.
the amount of permutations will be n!
hear is an example
R G B Y
R G Y B
R B G Y
R B Y G
R Y G B
R Y B G
G R B Y
? ? ? ?
? ? ? ?
please note im looking for permutations and not combinations as each element can only apear once.
any help on creating an algorithm for doing this would be apreciated. ive herd about a rotating door algorithm but the explanation was vague.
Thankyou
all permutations 1 by 1
Page 1 of 13 Replies  511 Views  Last Post: 17 June 2012  12:50 PM
Replies To: all permutations 1 by 1
#2
Re: all permutations 1 by 1
Posted 17 June 2012  11:38 AM
A recursive algorithm is a good approach here. Given a character array, the start index, and the end index, the idea is something of the following:
permute(char[] string, int start, int end) if start == end examine string for special properties return end if for i = 0 to (endstart), i = i+1 on each iteration swap(string, start, start+i) //make a swap permute(string, start+1, end) //now permute the rest of the array based on the change swap(string, start, start+i) //and now undo the swap end for end permute
#3
Re: all permutations 1 by 1
Posted 17 June 2012  12:29 PM
Thankyou macosxnerd101 for your reply. I will give this a go and see how far it gets me. i may be able to get good results with small n values.
#4
Re: all permutations 1 by 1
Posted 17 June 2012  12:50 PM
Page 1 of 1
