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

#1 shantics  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,608
  • 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


Was This Post Helpful? 0
  • +
  • -

#3 shantics  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#4 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,137
  • 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.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1