0

For a program Im writing I need to go through an array of objects with n entries. I need to check almost every combination. Lets say the lists contains {0,1,2,3} (Im matching the objects values to their index here for explenation). We fix the first one. This is the start value for all combinations. From 0 we choose one of the three objects left. This gives n! = 4! combinations but we consider the combinations 0 - 1 - 2 - 3 and 0 - 3 - 2 - 1 to be the same because their last (n-1) digits are the same in reverse order. With that the combination 0 - 2 - 1 - 3 and 0 - 3 - 1 - 2 give the same result and I dont have to look at both of them.

Do you know an effective way of getting an algorithm which gives me the j-th combination for j out of 1,...,(n-1)!/2 ?

Arjihad
  • 117
  • 7
  • Am I right to reduce your question to: "How do I efficiently generate a list of permutations of a range of numbers without generating an entry in that list which is also contained in reverse?" Because iterating through the range for the left most item is trivial if you solved the above mentioned problem. Am I right? – Matteo B. Dec 26 '18 at 00:26
  • 1
    I'm a bit lost on your definition of combinations. Could you provide an example of all "combinations" in order for your example list? – Dillon Davis Dec 26 '18 at 00:38
  • There are 4! *permutations* of four items. The algorithm for computing the nth permutation is described in https://stackoverflow.com/questions/7918806/finding-n-th-permutation-without-computing-others – Jim Mischel Dec 26 '18 at 14:23

0 Answers0