all permutations 1 by 1

Page 1 of 1

3 Replies - 783 Views - Last Post: 17 June 2012 - 12:50 PM

#1 shantics

Reputation: 0
• Posts: 31
• Joined: 17-March 12

all permutations 1 by 1

Posted 17 June 2012 - 09:12 AM

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

Is This A Good Question/Topic? 0

Replies To: all permutations 1 by 1

#2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12316
• Posts: 45,416
• Joined: 27-December 08

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 (end-start), 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 shantics

Reputation: 0
• Posts: 31
• Joined: 17-March 12

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 KYA

• Wubba lubba dub dub!

Reputation: 3202
• Posts: 19,233
• Joined: 14-September 07

Re: all permutations 1 by 1

Posted 17 June 2012 - 12:50 PM

For additional reference, I have some permutation snippets in our code section: in python, in C++, and in Java.