Generate unique ordered subsets from set based on condition

user_4539073 0
Viewed 96

Trying to tackle the generation of subsets inside of python for my Discrete Mathematics class. I have a set to split up into subsets which are ordered based on a specific condition and with a certain size.

As an example: Subset = {x1, x2, x3} ⊆ {5, 10, 15, 20, 25} and x1 < x2 < x3.

I would like to generate all possible subsets from the larger set, sized 3, and with the condition that they are ordered in ascension. There's a very good chance I'm overthinking the implementation of this. I currently have a working permutation generator but it basically generates all possible combinations. The code:

def perm(elements):
    if len(elements) <= 1:
        yield elements
    else:
        for i in range(len(elements)):
            for p in perm(elements[:i] + elements[i+1:]):
                yield [elements[i]] + p

I'd like to be able to modify this so that I can use this function to generate what I am looking for. I tried modifying the initial for loop's range but it ends up removing certain permutations which would be possible otherwise, and it's fair to say I am more stuck than making progress. Any help or advice would be appreciated.

discrete-mathematics python
1 Answers

Unless I'm misunderstanding what you're looking for itertools.combinations already implements the functionality of getting all unique subsets.

Assuming you're just looking for each combination to be sorted. As long as the initial input is sorted, the combinations will be as well.

import itertools

elements = sorted({5, 10, 15, 20, 25})
subset_size = 3
print(list(itertools.combinations(elements, subset_size)))

Produces:

[(5, 10, 15), 
 (5, 10, 20), 
 (5, 10, 25), 
 (5, 15, 20), 
 (5, 15, 25), 
 (5, 20, 25), 
 (10, 15, 20), 
 (10, 15, 25), 
 (10, 20, 25), 
 (15, 20, 25)]
user_154978880
Related