CODEWITHSUNDEEP
algorithmcombinations
zxc
zxc

Reputation: 15

Generate unique combinations of size N from an array of repeating characters

I have an array containing repeating characters. Take ['A','B','C','C'] as example. I am writing a C++ program to output all the combinations of size N.
When N = 2, program should output AB, AC, BC and CC.
When N = 3, program should output ABC, ACC, BCC.

My approach was to treat each character of the array as unique. I generated the all combinations and saved it to a vector. I then iterated through the vector to remove duplicate combinations.
For N = 2, assuming all characters are unique gives 4C2 = 6 possibilities : AB, AC, AC, BC, BC, CC.
1 AC and 1 BC are removed because they occur twice instead of once.

Is there a more efficient way to do this?

Note:

  1. The characters in the array are not necessarily in ascending order.
  2. In my initial approach, using find() for vector was insufficient to locate all duplicates. For array ['T','O','M','O','R','R','O','W'], the duplicates are permuted. For N = 4, two of the duplicates are TOMO and TMOO.

Upvotes: 0

Views: 849

Answers (1)

MBo
MBo

Reputation: 80267

You can sort source array and collect similar items in groups. In the code below I added index of the next group beginning to provide proper jump to the next group if next similar item is not used.

Python code and output:

a = ['T','O','M','O','R','R','O','W']
a.sort()
print(a)
n = len(a)
b = [[a[-1], n]]
next = n
for i in range(n-2,-1, -1):
    if a[i] != a[i+1]:
        next = i + 1
    b.insert(0, [a[i], next])
print(b)

def combine(lst, idx, n, k, res):
    if len(res) == k:
        print(res)
        return
    if idx >= n:
        return

    #use current item
    combine(lst, idx + 1, n, k, res + lst[idx][0])
    #omit current item and go to the next group   
    combine(lst, lst[idx][1], n, k, res)

combine(b, 0, n, 3, "")

['M', 'O', 'O', 'O', 'R', 'R', 'T', 'W']
[['M', 1], ['O', 4], ['O', 4], ['O', 4], ['R', 6], ['R', 6], ['T', 7], ['W', 8]]

MOO     MOR    MOT    MOW    MRR    MRT    MRW    MTW
OOO    OOR    OOT    OOW    ORR    ORT    ORW    OTW
RRT    RRW    RTW

Upvotes: 1

Related Questions