-1

I have to write a function that takes as input two numbers n and k and prints on the screen all the k-length subsets of a set created by n (order is not important), so basically a function that prints all the k-combinations of n.

For example: If n = 4 and k = 2 the initial set becomes (1,2,3,4) and it prints the following subsets:

(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)

I know that there is already a function that does that, but I have to create the function from scratch, so the use of the itertools or any other module is prohibited, and no, I can't copy the combinations function from the documentation and paste it on my code. As you may have understood, this is an assignement from my university, so I am not asking you to solve it for me and give me a code, I would like someone to explain to me how can I do it.

I know that it has to be done with a recursive function, because the number k is not known. I've also thought of 2 different solutions of how can I do this and I'm not sure if they're correct:

1st solution:

Create the powerset of the given set, and then remove all the subsets whose length is different than k.

2nd solution:

Populate a list with numbers from 1 to n^k, and then remove all the numbers that have duplicates in them. Then transform the numbers to strings and print them as sub-sets.

Sotiris Kettenis
  • 51
  • 1
  • 6
  • @ivan_pozdeev In the answer you have posted as possible duplication, they're using the function combinations() of the itertools module which I'm not allowed to use in my code. – Sotiris Kettenis Sep 29 '19 at 10:28
  • 1
    There are several answers there that don't use itertools or other libraries, e.g. [this one](https://stackoverflow.com/a/23743696/984421) and [this one](https://stackoverflow.com/a/41234915/984421) . – ekhumoro Sep 29 '19 at 10:30
  • A more serious objection to that other question being a duplicate is that this question wants only combinations of length `k` while the other question wants all combinations. So the other question is useful as part of the "1st solution" in this question but does not help otherwise. That said, I'm sure there must be real duplicate somewhere. – Rory Daulton Sep 29 '19 at 10:37
  • @RoryDaulton The OP asked for a "howto", not solutions/code. If they can't work it out from all the answers given there, they can come back with a more specific question. As it is, the current question is arguably too broad anyway. – ekhumoro Sep 29 '19 at 10:46

1 Answers1

0

Try this code:

def combinations(l, k):
    if k <= 0:
        comb = [None]
    else:
        comb = []
        for i, item in enumerate(l, 1):
            rem_items = l[i:]
            rem_comb = combinations(rem_items, k-1)
            comb.extend(item if c is None else (item, c) for c in rem_comb)
    return comb

n = 4
k = 2
combinations(range(1,n), k)
# [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
Massifox
  • 4,369
  • 11
  • 31