1

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.

Improve this question
5
  • n! gets pretty big pretty fast. How big are your lists? Commented Aug 15, 2012 at 19:58
  • There's no difference between characters in a string and nodes in a list when you're talking about permutations. Commented Aug 15, 2012 at 20:00
  • Did you try to google on alforithm of all permutations? Thats actually whta you need Commented Aug 15, 2012 at 20:01
  • codereview.stackexchange.com/questions/11598/… Commented Aug 15, 2012 at 20:04
  • I don't need more than a small number. In practice I'm not going to go further than the 24 permutations of a 4 element set. Commented Aug 15, 2012 at 23:07

2 Answers 2

Reset to default
7

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!

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I skimmed through the presentation.It is easier to implement the OP question that read it thoroughly!Perhaps you could edit your answer and give some small intro about the presentation and how it helps.It seems interesting
+1 - This is also known as 'permutation mapping' - Google should lead to alternate implementations
4

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.)

Improve this answer

1 Comment

Thanks. This should do what I need it to.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.