I have three places, and each place can take a value from the set {1, 2, 3}. I am using the following python script to generate all the possible product:

import itertools

options = [1, 2, 3]
for element in itertools.product(options, options, options):
  print(element)

Output:

(1, 1, 1)
(1, 1, 2)
(1, 1, 3)
(1, 2, 1)
(1, 2, 2)
(1, 2, 3)
(1, 3, 1)
(1, 3, 2)
(1, 3, 3)
(2, 1, 1)
(2, 1, 2)
(2, 1, 3)
(2, 2, 1)
(2, 2, 2)
(2, 2, 3)
(2, 3, 1)
(2, 3, 2)
(2, 3, 3)
(3, 1, 1)
(3, 1, 2)
(3, 1, 3)
(3, 2, 1)
(3, 2, 2)
(3, 2, 3)
(3, 3, 1)
(3, 3, 2)
(3, 3, 3)

However, in my use case I'd like to eliminate a few of these products. For example,

1. If I have considered (1, 1, 1) to be an output, then we can eliminate (2, 2, 2) and (3, 3, 3). Since both have the same configuration: All places have the same number.
2. If I have considered (1, 1, 2) to be an output, then we can eliminate (2, 2, 3), (2, 2, 1), (1, 2, 1), (3, 1, 3). Since all of them have the configuration of: Two places should have the same number.

CodePudding user response：

What you're looking for is the partitions of a number, mapped to elements of a set.

In your case, we want 3 elements, so N=3. We then find all ways that we can sum positive integers to equal three, and allow the ith integer to represent the count of the ith element of the set present.

In this case, I'm going to use partition-generating code from Python Algorithms and Data Structures by David Eppstein:

def revlex_partitions(n):
    """
    Integer partitions of n, in reverse lexicographic order.
    The output and asymptotic runtime are the same as mckay(n),
    but the algorithm is different: it involves no division,
    and is simpler than mckay, but uses O(n) extra space for
    a recursive call stack.
    """
    if n == 0:
        yield []
    if n <= 0:
        return
    for p in revlex_partitions(n-1):
        if len(p) == 1 or (len(p) > 1 and p[-1] < p[-2]):
            p[-1]  = 1
            yield p
            p[-1] -= 1
        p.append(1)
        yield p
        p.pop()

With this, we now just need to iterate over these partitions, and map the values:

def configurations(elements, count):
    for partition in revlex_partitions(count):
        if len(partition) <= len(elements):
            yield tuple(x for x, c in zip(elements, partition) for _ in range(c))

Examples:

>>> print(list(configurations({14, 23, 55, 78}, 4)))
[(14, 14, 14, 14), (14, 14, 14, 23), (14, 14, 23, 23), (14, 14, 23, 78), (14, 23, 78, 55)]
>>> print(list(configurations({1, 2, 3}, 4)))
[(1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 2, 2), (1, 1, 2, 3)]

Performance notes:

Asymptotically speaking, this there are an exponential number of partitions of a number, so of course the run time will be exponential. I tried some of my own modifications to the above partition algorithm (pruning elements that wouldn't meet the size requirement in advance), but was only ever able to achieve around a 4x speedup, and that was for fairly large inputs taking seconds or more.

There's also an iterative implementation of the partition function in the links above, but its also much more complex- if performance is an issue, consider trying that one.