0

I need to take all possible unique combinations of 3 elements in a vector. std::next_permutation works, but it gives me lot of duplicates.

For example

(1, 2, 3, 4, 5) and (1, 2, 3, 5, 4)

first 3 elements that I take are equal, so I'm doing redundant work. Is there any efficient way of iterating through the unique combinations?

axe
  • 2,331
  • 4
  • 31
  • 53
  • 6
    Those two are not 'duplicates'. A permutation includes all elements *by definition*. If you want something that is not really permutations, you have to either look for the correct name of what you want, or describe it more clearly :) – us2012 Mar 01 '13 at 23:54
  • 1
    I think he wants all permutations of the [N over K combinations](http://en.wikipedia.org/wiki/Combination). – ipc Mar 01 '13 at 23:56
  • @ipc Hm, good spot, but I guess he may only want the combinations, not the permutations of the combinations. Let's wait for him to tell us what he actually wants. – us2012 Mar 01 '13 at 23:59
  • @ipc: Yes. That's right. Thanks for mentioning the right name :) this is very helpful. – axe Mar 01 '13 at 23:59
  • Here is it guys. http://stackoverflow.com/questions/12991758/creating-all-possible-k-combinations-of-n-items-in-c Thanks very much. – axe Mar 02 '13 at 00:04

1 Answers1

-1

First you have to figure out the number N of combinations of k objects you can pick out of b objects.

N = b! / (b - k)!

Next you find all the combinations by iterating over your initial list and filling N containers in total with all those combinations.

smac89
  • 39,374
  • 15
  • 132
  • 179