0

I need to come up with an algorithm that generates all Unordered combinations of a set of Datapoints.

Let me give an example of say [0 1 2]

All the following are possible:

[(0,1,2)]
[(0,1) (2)] [(0,2) (1)] [(1,2) (0)]
[(0), (1), (2)]

For say [0 1 2 3] it gets alot more complicated

[(0,1,2,3)]
[(0,3) (1,2)] [(0,1) (3,2)] [(0,2) (3,1)] 
[(0,3,1) (2)] [(0,1,3) (2)] [(0,2,3) (1)]
[(0,3) (1) (2)] [(0,1) (3) (2)] [(0,2) (3) (1)]
[(1,2) (0) (3)] [(3,2) (1) (0)] [(3,1) (2) (0)]
[(0) (1) (2) (3)]

Something like this. I need a general solution to this problem for any size. I know it blows up to a larger number, but I need to generate this. How would I approach this problem?

raaj
  • 2,869
  • 4
  • 38
  • 58
  • Why is `[(0,1) (2)]` a possible output? This doesn't look like a "combination" in the normal sense of the word. Please explain your problem as specifically as possible. – kaya3 Jan 28 '20 at 22:08
  • Yes, youre right in that its not a combination. I need to devise an algorithm for this special case. We have a sensor that is trying to fire a laser beam onto N targets at once. We need to hit everyone of the targets, but sometimes we need multiple steps to hit all targets. so [(0,1) (2)] and [(0,1,2)] are valid solutions – raaj Jan 28 '20 at 22:16
  • OK, but then why is `[(0)]` also a possible output? – kaya3 Jan 28 '20 at 22:20
  • oh sorry i will edit the question it is suppose to be [(0) (1) (2)]. we are working in python so we have access to the itertools library if that helps – raaj Jan 28 '20 at 22:20
  • 1
    Does this answer your question? [How to find all partitions of a set](https://stackoverflow.com/questions/20530128/how-to-find-all-partitions-of-a-set) – kaya3 Jan 28 '20 at 22:28
  • Interesting..i think it might. Its a shame they dont have a Python solution there – raaj Jan 28 '20 at 22:32
  • [This question](https://stackoverflow.com/questions/8646186/yielding-sub-combinations/) works for Python; [this other one](https://stackoverflow.com/questions/59303187/how-to-iterate-through-all-partitions-of-a-list-with-a-condition-on-the-subsets) suggests that the `sympy` library has a function that works, too. – kaya3 Jan 28 '20 at 22:44
  • Great. Just a final question. Do you think a solution exists out there that doesn't use yield and generators? Eventually i need to port it to C++ that is why – raaj Jan 28 '20 at 23:10

0 Answers0