Creating a list of all possible combinations from a set of items for n combination sizes

Question

Apologies in advance if the wording of my question is confusing. I've been having lots of trouble trying to explain it.

Basically I'm trying to write an algorithm that will take in a set of items, for example, the letters in the alphabet and a combination size limit (1,2,3,4...) and will produce all the possible combinations for each size limit.

So for example lets say our set of items was chars A,B,C,D,E and my combination limit was 3, the result I would have would be:

A,   
AB, AC, AD, AE,
ABC, ABD, ABE, ACD, ACE, ADE,
B,
BC, BD, BE,
BCD, BCE, BDE,
C,
CD, CE,
CDE,
D, 
DE,
E

Hopefully that makes sense.

For the context, I want to use this for my game to generate army compositions with limits to how many different types of units they will be composed of. I don't want to have to do it manually!

Could I please gets some advice?

Answer 1

A recursion can do the job. The idea is to choose a letter, print it as a possibility and combine it with all letters after it:

#include <bits/stdc++.h>    
using namespace std;

string letters[] = {"A", "B", "C", "D", "E"};
int alphabetSize = 5;
int combSizeLim = 3;

void gen(int index = 0, int combSize = 0, string comb = ""){
    if(combSize > combSizeLim) return;
    cout<<comb<<endl;
    for(int i = index; i < alphabetSize; i++){
        gen(i + 1, combSize + 1, comb + letters[i]);
    }
}

int main(){
    gen();
    return 0;
}

OUTPUT:

A                                                                                                                                                                                  
AB                                                                                                                                                                                 
ABC                                                                                                                                                                                
ABD                                                                                                                                                                                
ABE                                                                                                                                                                                
AC                                                                                                                                                                                 
ACD                                                                                                                                                                                
ACE                                                                                                                                                                                
AD
ADE                                                                                                                                                                                
AE                                                                                                                                                                                 
B                                                                                                                                                                                  
BC                                                                                                                                                                                 
BCD                                                                                                                                                                                
BCE                                                                                                                                                                                
BD                                                                                                                                                                                 
BDE                                                                                                                                                                                
BE                                                                                                                                                                                 
C                                                                                                                                                                                  
CD                                                                                                                                                                                 
CDE                                                                                                                                                                                
CE                                                                                                                                                                                 
D                                                                                                                                                                                  
DE                                                                                                                                                                                 
E 

Answer 2

Here's a simple recursive solution. (The recursion depth is limited to the length of the set, and that cannot be too big or there will be too many combinations. But if you think it will be a problem, it's not that hard to convert it to an iterative solution by using your own stack, again of the same size as the set.)

I'm using a subset of Python as pseudo-code here. In real Python, I would have written a generator instead of passing collection through the recursion.

def gen_helper(collection, elements, curr_element, max_elements, prefix):
    if curr_element == len(elements) or max_elements == 0:
        collection.append(prefix)
    else:
        gen_helper(collection, elements, curr_element + 1,
                 max_elements - 1, prefix + [elements[curr_element]])
        gen_helper(collection, elements, curr_element + 1,
                 max_elements, prefix)

def generate(elements, max_elements):
    collection = []
    gen_helper(collection, elements, 0, max_elements, [])
    return collection

The working of the recursive function (gen_helper) is really simple. It is given a prefix of elements already selected, the index of an element to consider, and the number of elements still allowed to be selected.

If it can't select any more elements, it must choose to just add the current prefix to the accumulated result. That will happen if:

• The scan has reached the end of the list of elements, or
• The number of elements allowed to be added has reached 0.

Otherwise, it has precisely two options: either it selects the current element or it doesn't. If it chooses to select, it must continue the scan with a reduced allowable count (since it has used up one possible element). If it chooses not to select, it must continue the scan with the same count.

Since we want all possible combinations (as opposed to, say, a random selection of valid combinations), we need to make both choices, one after the other.