Cartesian product but remove duplicates up to cyclic permutations

Question

Given two integers n and r, I want to generate all possible combinations with the following rules:

• There are n distinct numbers to choose from, 1, 2, ..., n;
• Each combination should have r elements;
• A combination may contain more than one of an element, for instance (1,2,2) is valid;
• Order matters, i.e. (1,2,3) and (1,3,2) are considered distinct;
• However, two combinations are considered equivalent if one is a cyclic permutation of the other; for instance, (1,2,3) and (2,3,1) are considered duplicates.

Examples:

n=3, r=2
11 distinct combinations
(1,1,1), (1,1,2), (1,1,3), (1,2,2), (1,2,3), (1,3,2), (1,3,3), (2,2,2), (2,2,3), (2,3,3) and (3,3,3)

n=2, r=4
6 distinct combinations
(1,1,1,1), (1,1,1,2), (1,1,2,2), (1,2,1,2), (1,2,2,2), (2,2,2,2)

What is the algorithm for it? And how to implement it in c++? Thank you in advance for advice.

Answer 1

Here is a naive solution in python:

• Generate all combinations from the Cartesian product of {1, 2, ...,n} with itself r times;
• Only keep one representative combination for each equivalency class; drop all other combinations that are equivalent to this representative combination.

This means we must have some way to compare combinations, and for instance, only keep the smallest combination of every equivalency class.

from itertools import product

def is_representative(comb):
    return all(comb[i:] + comb[:i] >= comb
               for i in range(1, len(comb)))

def cartesian_product_up_to_cyclic_permutations(n, r):
    return filter(is_representative,
                  product(range(n), repeat=r))

print(list(cartesian_product_up_to_cyclic_permutations(3, 3)))
# [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 1), (0, 1, 2), (0, 2, 1), (0, 2, 2), (1, 1, 1), (1, 1, 2), (1, 2, 2), (2, 2, 2)]

print(list(cartesian_product_up_to_cyclic_permutations(2, 4)))
# [(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 1), (0, 1, 0, 1), (0, 1, 1, 1), (1, 1, 1, 1)]

You mentioned that you wanted to implement the algorithm in C++. The product function in the python code behaves just like a big for-loop that generates all the combinations in the Cartesian product. See this related question to implement Cartesian product in C++: Is it possible to execute n number of nested "loops(any)" where n is given?.