Picking all possible cases.

You are give an array containing 'n' elements. You are given an integer k (input). You must find all possible sets of 'k' elements from the 'n' elements. How to do this?

Ex: Given array as {1,2,3}. k=2. The possible sets are {1,2},{1,3}and {2,3}.

P.S.: Please try not to give just a piece of code without telling how and why it works. Any idea as to how to approach this will also be much appreciated.
One idea is to create a bit string of length n with k elements set to 1.
For your example it will be "011". After that you need to find all permutations of this string and extract corresponding values from array. For your case:
array:       1 2 3   1 2 3   1 2 3
permutation: 0 1 1   1 0 1   1 1 0
result:     (  2 3) (1   3) (1 2  )
You can use next_permutation from standard library. http://en.cppreference.com/w/cpp/algorithm/next_permutation
You need to have 'k' nested loops. Loop through the entire array in the outer loop. Each inner loop will loop through the elements beyond the immediately containing loop. For instance, if one loop is currently on the 3rd element, the nested loop will loop from the 4th element to the end. The nesting of the loops would probably be best done using recursive function calls.

When you reach the innermost loop, take the current values for each of the loops to create your set.

p.s. By the way, if the same value can be in the original array multiple times (e.g. {1, 2, 1}), then there is more checking to be done. The correct answer would be {1,2}, {1,1}. The above algorithm would give you {1,2}, {1,1}, {2,1}, where the 1st and 3rd values are equivalent.

The correct answer would be {1,2}, {1,1}.
This is not strictly correct in all cases. There is a question whether value of elements matters (so is it sequence with repetitions or without repetitions where some elements happens to map to the same value; or simply if we are choosing indexes and extacting elements from them). To determine what actually is needed, what constraints are and other stuff there should be more information provided in op post. Like two more pages.
Welcome to the world of math

(Also you could hust delete duplicates after initial run. By std::unique)
Last edited on
@doug4 ,@MiiNiPaa the problem is this. I have tried nested loops, but i get sets like {2,2} and {3,3}. I dont' want these types of sets. I also don't want both sets like {1,2} and {2,1}. This is just a repetition. I thought of replacing the chosen elements by null, but this drastically reduces the number of possible sets. (Like, i replace 1 by null, i can't get the other set which contains 1). I thought of using random function. But, i dont know how to extract 'k' different random elements from an array.
You did not answer doug4 question. If there is no repetitive element in original array, then both our suggestions will work as you want without further tuning.
Registered users can post here. Sign in or register to post.