Reputation: 21

How to remove same elements with different orders in a list?

For example, I'm working on a method that given a certain size "k", and an integer "n" I can generate subsets from {1...n} with "k" length.

This is my code so far:

def combinations(k,lista,comb):
    if(len(comb)==k):
        print(comb)
    else:
        for i in range(len(lista)):
            combinations(k,lista,comb + str(lista[i]))
def starter(n,k):
    lista = []
    for i in range(1,n+1):
        lista.append(i)
    combinations(k,lista,"")

starter(5,3)

The output of starter(5,3) is:

My problem is that it is repetitive, as you see I have 545 and 554 in the output(and 455;not shown), while in this case ordering shouldn't matter, therefore I should keep either 545 or 554 or 455. I also have 332 in the output as well as 323 and 233, these three are considered "duplicates" and I need to keep only one.

How can my code be modified to filter for this?

Edit: in my code "k" was "m", I fixed it to avoid misconceptions.

Edit2: I do understand that I can use itertools, but I am trying to solve everything(for now) without depending on libraries or packages.

Upvotes: 0

Answers (5)

norok2

Reputation: 26886

In this case, the standard library is a great place to look for info. There, the documentation reports many equivalent implementation in plain Python of the available functions like itertools.combinations() and itertools.combinations_with_replacement()

These are significantly more efficient than the solution proposed so far in this question.

Upvotes: 0

brentertainer

Reputation: 2188

A lot of times when recursion is involved, I like to keep track of the state in an outer function and use a nested/inner function to actually perform the recursion. Here, the state consists of the level (between 0 and k - 1), a stack, and the max yielded stack (to ensure no duplicates as you asked.)

With replacement:

def my_combinations_with_replacement(n, k):

    stack = list()
    maxstack = tuple()
    d = 0

    def _helper():
        nonlocal d, maxstack, stack
        for i in range(n):
            stack.append(i)
            if len(stack) == k:
                if tuple(sorted(stack)) > maxstack:
                    maxstack = tuple(sorted(stack))
                    yield maxstack
            else:
                d += 1
                yield from _helper()
                d -= 1
            stack.pop()

    return [''.join(map(str, x)) for x in _helper()]

Without replacement:

def my_combinations(n, k):

    stack = list()
    maxstack = tuple()
    d = 0

    def _helper():
        nonlocal d, maxstack, stack
        for i in range(d, n):
            if i not in stack:
                stack.append(i)
                if len(stack) == k:
                    if tuple(sorted(stack)) > maxstack:
                        maxstack = tuple(sorted(stack))
                        yield maxstack
                else:
                    d += 1
                    yield from _helper()
                    d -= 1
                stack.pop()

    return [''.join(map(str, x)) for x in _helper()]

Output:

>>> my_combinations_with_replacement(5, 3)
['000', '001', '002', '003', '004', '011', '012', '013', '014', '022', '023',
 '024', '033', '034', '044', '111', '112', '113', '114', '122', '123', '124',
 '133', '134', '144', '222', '223', '224', '233', '234', '244', '333', '334',
 '344', '444']
>>> my_combinations(5, 3)
['012', '013', '014', '023', '024', '034', '123', '124', '134', '234']

Upvotes: 0

Adrián

Reputation: 3

The first solution that comes to my mind is mapping these numbers to a dictionary, where every digit is the key (1,2,3,...,9) and the values is the count of each digit in the given number. This way you're not taking into account the order of the digits but rather the number of times they appear in a certain number.

You just have to write a function that takes an integer as an input, iterate over it by transforming it into a string and then count each digit into a dictionary.

>>> n = 1233657
>>> digits = [int(d) for d in str(n)]           
>>> digits
[1, 2, 3, 3, 6, 5, 7]
>>> digit_count = dict.fromkeys(digits, 0)
for d in digits:
... digit_count[d] += 1
... 
>>> digit_count
{1: 1, 2: 1, 3: 2, 5: 1, 6: 1, 7: 1}

You'll have a dictionary with all combinations of numbers as keys and the representation explained before as values. Then you just have to group the different numbers that map to the same dictionary and choose one given your desired criteria.

Upvotes: 0

Diptangsu Goswami

Reputation: 5965

I've used your code and made one modification to reach your solution. I'm sorting the values and storing it in a set. Sorting the values will ensure that the values 545, 554 or 455 all get sorted to 455. A set cannot contain duplicate values which means it'll only be added once. This does not reduce the time complexity of your algorithm because it does not generate less values, it simply does not add duplicate values and only the unique values are stored.

values = set()


def combinations(k, lista, comb):
    if(len(comb) == k):
        # print(comb)
        value = ''.join(sorted(comb))
        values.add(value)
    else:
        for i in range(len(lista)):
            combinations(k, lista, comb + str(lista[i]))


def starter(n, k):
    lista = []
    for i in range(1, n + 1):
        lista.append(i)
    combinations(k, lista, "")


starter(5, 3)
print(values)

Output:

{'122', '245', '145', '355', '111', '235', '223', '233', '113', '224', '144', '333', '134', '112', '445', '125', '255', '225', '155', '234', '345', '123', '444', '455', '222', '115', '344', '133', '114', '335', '124', '334', '135', '244', '555'}

Upvotes: 1

ivallesp

Reputation: 2212

I'd use rather itertools functions for that. Does this function work for you?

from itertools import combinations
list(combinations([1,2,3,4,5,6,7,8,9,0], 3))

More info on itertools functions here: https://docs.python.org/2/library/itertools.html#itertool-functions

Upvotes: 1

How to remove same elements with different orders in a list?

Answers (5)

Related Questions