There are n types to choose from and r numbers chosen, but combinations from it are not typical combinations. It's something like: r are items in your circle and n are shapes of these items and you must find all the ways to arrange it.

For example, for n=3, r=3 you have 11 options: (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)

For n=2, r=4 you have 6 options:(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.

CodePudding user response：

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