Generate unique combinations of length k from string-CodePudding

Lets say we have the string aabc. If you take two chars from this string without replacement, your result will be in the set {aa, ab, ac, bc}. I'm trying to develop an algorithm to construct this set. It's important that there be no duplicates. The algorithm if all chars are unique is simple, but it gets more complicated if there are duplicates. I came up with this, but I'm curious if there are simpler solutions:

from collections import Counter

class Solution(object):
    def combinations(self, s, k):
        s = Counter(s)
        self.res = []
        self.combo_helper('', s, k)
        return self.res
    
    def combo_helper(self, used, remaining, k):
        if k == 0:
            self.res.append(used)
        else:
            new = remaining.copy()
            for n in remaining:
                if remaining[n]:
                    new[n] -= 1
                    self.combo_helper(
                        used n, new, k-1
                    )
                    new = new.copy()
                    new[n] = 0

CodePudding user response：

I took the recommendation of @Pychopath and checked out the more-itertools approach to the problem. They take a bottom-up DP approach, and I figured I'd translate it back into the top-down approach I originally took. Unfortunately, it requires you to sort the iterable first

class Solution:
    def first_char_idx(self, s, start=0):
        ''''
        Returns first idx and char of string
        aabbc -> [(0, a), (2, b), (4, c)]
        '''
        seen = set()
        return [(idx, c) for idx, c in enumerate(s, start) if c not in seen and not seen.add(c)]
        
    def unique_combos_helper(self, used, idx, k):
        if not k:
            self.res.append(used)
        else:
            for i, c in self.first_char_idx(self.pool[idx:], idx):
                self.unique_combos_helper(used c, i 1, k-1)

    def unique_combos(self, s, k):
        s = sorted(list(s))
        self.res = []
        self.pool = s
        self.unique_combos_helper("", 0, k)
        return self.res

CodePudding user response：

A set doesn't allow duplicates, so, you can do it as a list and just convert to a set.

In a list, with duplicates, your result taking all the possibilities will jave duplicates ['aa', 'ab', 'ac', 'ab', 'ac', 'bc'], but if you convert do a set, it will not:

x='aabc'
b=list()
for i in range(len(x)-1):
  for j in range(i 1,len(x)):
    b.append(x[i] x[j])
b=set(b)

CodePudding user response：

Change the length according to your needs:

import itertools

list='aabc'
lenght=2

result=[''.join(p) for p in itertools.product(list, repeat=lenght)][::-1]