CODEWITHSUNDEEP
algorithmcombinationscartesian-productcircular-permutations
user19044944
user19044944

Reputation:

Cartesian product but remove duplicates up to cyclic permutations

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

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.

Upvotes: -1

Views: 302

Answers (1)

Stef
Stef

Reputation: 15505

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?.

Upvotes: 1

Related Questions