CODEWITHSUNDEEP
javaalgorithmpermutation
Travis Nell
Travis Nell

Reputation: 11

Iterating over Permutations of an Array

I'm working on some java code for some research I'm working on, and need to have a way to iterate over all permutations of an ArrayList. I've looked over some previous questions asked here, but most were not quite what I want to do, and the ones that were close had answers dealing with strings and example code written in Perl, or in the case of the one implementation that seemed like it would work ... do not actually work.

Ideally I'm looking for tips/code snippets to help me write a function permute(list, i) that as i goes from 0 to list.size()! gives me every permutation of my ArrayList.

Upvotes: 1

Views: 13991

Answers (2)

Petr
Petr

Reputation: 63419

If iterating over all permutations is enough for you, see this answer: Stepping through all permutations one swap at a time . For a given n the iterator produces all permutations of numbers 0 to (n-1). You can simply wrap it into another iterator that converts the permutation of numbers into a permutation of your array elements. (Note that you cannot just replace int[] within the iterator with an arbitrary array/list. The algorithm needs to work with numbers.)

Upvotes: 4

templatetypedef
templatetypedef

Reputation: 373482

There is a way of counting from 0 to (n! - 1) that will list off all permutations of a list of n elements. The idea is to rewrite the numbers as you go using the factorial number system and interpreting the number as an encoded way of determining which permutation to use. If you're curious about this, I have a C++ implementation of this algorithm. I also once gave a talk about this, in case you'd like some visuals on the topic.

Hope this helps!

Upvotes: 7

Related Questions