Menu
I need to calculate permutations iteratively. The method signature looks like:
int[][] permute(int n)
For n = 3 for example, the return value would be:
[[0,1,2], [0,2,1], [1,0,2], [1,2,0], [2,0,1], [2,1,0]] How would you go about doing this iteratively in the most efficient way possible? I can do this recursively, but I'm interested in seeing lots of alternate ways to doing it iteratively.
200
To calculate the number of permutations, take the number of possibilities for each event and then multiply that number by itself X times, where X equals the number of events in the sequence. For example, with four-digit PINs, each digit can range from 0 to 9, giving us 10 possibilities for each digit.
You take first element of an array (k=0) and exchange it with any element (i) of the array. Then you recursively apply permutation on array starting with second element. This way you get all permutations starting with i-th element.
For example, for <A,B,C>, the swap sequence 012 leaves all items in place, while 122 starts by swapping index 0 with index 1, then swaps 1 with 2, and then swaps 2 with 2 (i.e. leaves it in place). This results in the permutation BCA.
see QuickPerm algorithm, it's iterative : http://www.quickperm.org/
Edit:
Rewritten in Ruby for clarity:
def permute_map(n) results = [] a, p = (0...n).to_a, [0] * n i, j = 0, 0 i = 1 results << yield(a) while i < n if p[i] < i j = i % 2 * p[i] # If i is odd, then j = p[i], else j = 0 a[j], a[i] = a[i], a[j] # Swap results << yield(a) p[i] += 1 i = 1 else p[i] = 0 i += 1 end end return results end If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
