How to find all combinations of all items in a set? [closed]

Let's say, there's a Product data-model. Product has the attribute - colour, which can, in this case, be red, black, yellow, white, orange. And which in total amounts to 5 different Products.

Now I want to introduce a new set of attributes, let's say, material - cotton, nilon, paper; and size - s, m, l, xl; this will amount to a bigger set of different Products, each of which of a different colour, material and size.

In total, there'll be 60 different combinations: 5 colours * 3 materials * 4 sizes = 60. Right?

Later I may want to introduce more attributes as well, therefore, a solution should not rely on the amount of attributes as a constant, because it's a variable.

Q:

What'll be an algorithm for creating a set of Products with all these attributes?

And is there a name for it?

The amount of attributes and their values become known at runtime only. And the amount of values of each attribute differ: one attribute can have A values, other B, other C...

update1

Trying to implement it using the odometer algorithm,I've created an array of integers:

``````--------------------------------------------------
3 (colour) |  4 (material)  | 5 (size) | 2 (design)
--------------------------------------------------
``````

that is:

3 is the amount of colour values: red, blue, black

4 is the amount of materials: cotton, paper, iron, gold

5 is the amount of sizes: s, m, l, xl, xxl

2 is the amount of design values: cool, excellent

and so on..

This has been suggested:

`You always start with incrementing the first array entry by one, until it gets an overflow...[...]`

but what would it give me?

``````unique_variants = []
for i in my_array:
# i = 3 ===> ++ 3 new variants
# i = 4 ===> ++ 4 new variants
# i = 5 ===> ++ 5 new variants
# i = 2 ===> ++ 2 new variants

# [......]

====>
3 + 4 + 5 + 2 = 14 unique variants (wrong)
``````

that is, it'd be a sum, whereas what I need is to multiply, thus creating 120 unique variants:

``````3 * 4 * 5 * 2 = 120 unique variants (right)
``````

Or, better yet, I need those unique combinations themselves, for instance:

• product1 (red, iron, m, cool)
• product2 (red, paper, m, cool)
• product3 (blue, iron, s, excellent)
• .....
• product N (black, gold, xxl, excellent)

....

• What you're missing is that when an array entry gets an overflow, it gets reset, and the process repeats: after (black, cotton, s, cool) you get (red, paper, s, cool), and after that (blue, paper, s, cool) and so on. This will generate all 120 variants, and is equivalent to Doc Browns's odometer, at a different level of abstraction. Jun 13, 2021 at 13:19
• @Jasmijn how precisely? Doc Brown's solution is difficult to follow as there're some things omitted that are, probably, too obvious to him, therefore, I have a half of a solution now Jun 13, 2021 at 14:01
• It's hard to fill in the missing code at this high level of abstraction as the devil is in the details, but basically you'd add a copy of `a` to your output. Jun 13, 2021 at 17:15

The name for this is Cartesian product.

Python has a function for this, and the documentation for it shows code that's roughly equivalent to what the function itself does:

``````def product(*args, repeat=1):
# product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
# product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
pools = [tuple(pool) for pool in args] * repeat
result = [[]]
for pool in pools:
result = [x+[y] for x in result for y in pool]
for prod in result:
yield tuple(prod)
``````

Or, if you're using Python, you could just use `itertools.product`.

Lets say there are n different attributes, the first one having k1 different values, the second one k2, ..., the n-th one kn.

The most straightforward algorithm here is to implement an odometer. Just create an integer array with n entries. The i-th entry is going to run through the values 0,..., ki-1. You always start with incrementing the first array entry by one, until it gets an overflow which causes it to be reset to zero and the second entry to be incremented by one, until it gets an overflow, then increment the third entry, and so on. In pseudocode (`a` is the array holding the "odometer digits", starting with all elements set to zero. `k` is the array holding the number of values for each attribute):

`````` p=1;
for(i=0;i<n;++i)
{
p*=k[i];
a[i]=0;
}

for(j=0;j<p;++j)
{
//...
// Add some code here which takes the current state
// of the array a and maps it to a product object
// with the corresponding attribute values.
//...
for(i=0;i<n;++i)
{
a[i]++;
if(a[i] < k[i])
break;
a[i]=0;
}
}
``````

This will produce all k1 x ... x kn combinations.

I leave it as an exercise to you to create the different products from an "odometer state".

• I don't understand - what do I actually a) do an each increment b) how I increment it? Jun 13, 2021 at 7:37
• @RayanLemi: do you know what an odometer is and have an idea, how to implement it, lets say, with the usual digits from 0 to 9? Jun 13, 2021 at 7:39
• an odometer is a device in a car; odometer algorithm - not yet, but I can do a research Jun 13, 2021 at 7:42
• @RayanLemi: I think before googling this, you should really try to implement this by yourself. Jun 13, 2021 at 7:44
• look at my update please Jun 13, 2021 at 9:35

Suppose each attribute can be modeled as a nonnegative integer in some range, [0, max(k)], for the kth attribute. Suppose further the list of attributes is modeled as an array of length n such that the kth value of the array is the value of the kth attribute. For example, if you have two attributes, color and size, and color is red or green and size is skall, medium or large, the array [0, 1] might represent red and medium.

A recursive solution to enumerate all possible array values is this:

``````EnumerateAll()
EnumerateAllInternal(new uint[n], 0)

EnumerateAllInternal(soln, place)
if place >= n then
print soln
else
for i = 0 to max(place)
soln(place) = i
EnumerateAll(soln, place + 1)

call Enumerate()
``````

This recursive solution works by performing depth-first search on an implicit tree whose non-root nodes are the values the attributes can take.

• what is `soln`? and what's `place`? Jun 13, 2021 at 13:22
``````for(color: colorList) {
for(material: materialList) {
products.append(new Product(color, material))
}
}
``````

"nested for loop" I will call it. Whenever you add another property to the product, add a new list and a loop. It is stupid, but it will work.

EDIT: I don't know what this is or how it is called, but I think it does what you want it to do.

``````public class AttributeGeneration
class Attribute {}

class Attribute1 extends Attribute
{
String prop;

public Attribute1(String prop)
{
this.prop = prop;
}

@Override
public String toString()
{
return "Attribute1{" +
"prop='" + prop + '\'' +
'}';
}
}

class Attribute2 extends Attribute
{
String prop;

public Attribute2(String prop)
{
this.prop = prop;
}

@Override
public String toString()
{
return "Attribute2{" +
"prop='" + prop + '\'' +
'}';
}
}

class Builder
{
Attribute1 attribute1;
Attribute2 attribute2;

public Builder withAttribute(Attribute attribute)
{
if (attribute instanceof Attribute1)
{
this.attribute1 = (Attribute1) attribute;
}
else if (attribute instanceof Attribute2)
{
this.attribute2 = (Attribute2) attribute;
}

return this;
}

public Target build()
{
return new Target(attribute1, attribute2);
}
}

class Target
{
Attribute1 attribute1;
Attribute2 attribute2;

public Target(
Attribute1 attribute1,
Attribute2 attribute2
)
{
this.attribute1 = attribute1;
this.attribute2 = attribute2;
}

@Override
public String toString()
{
return "Target{" +
"attribute1=" + attribute1 +
", attribute2=" + attribute2 +
'}';
}
}

static List<Target> result = new ArrayList<>();

class Constatns
{
List<Attribute1> attribute1s = List.of(
new Attribute1("A1P1"),
new Attribute1("A1P2"),
new Attribute1("A1P3")
);
List<Attribute2> attribute2s = List.of(
new Attribute2("A2P1"),
new Attribute2("A2P2"),
new Attribute2("A2P3")
);
List<List<? extends Attribute>> attributes = List.of(attribute1s, attribute2s);
}

public void generate(
List<List<? extends Attribute>> attributeList,
int depth,
Builder builder
)
{
List<? extends Attribute> attributes = attributeList.get(depth);

for (Attribute attribute :
attributes)
{
builder.withAttribute(attribute);

if (isLeaf(attributeList, depth))
{
}
else
{
generate(attributeList, depth + 1, builder);
}
}
}

private boolean isLeaf(
List<List<? extends Attribute>> attributeList,
int depth
)
{
return depth == attributeList.size() - 1;
}

@Test
@Tag("special")
void test()
{
var constants = new Constatns();

generate(constants.attributes, 0, new Builder());

System.out.println(result);
System.out.println(result.size());
}
}

``````

You can run the above code with JUnit if you want.

My idea was to recursively walk over all "branches" and generate the target class in the leafs. The builder is basically an object that represents the state of the Target class at a certain node.

• .that is wrong. Jun 13, 2021 at 7:35
• You seemed to have missed the OPs edit: "a solution should not rely on the amount of attributes as a constant, because it's a variable." Jun 13, 2021 at 7:38
• I understood that as "number of attributes of the list", no as the number of lists. I'll update my post. Jun 13, 2021 at 9:40
• I don't use Java, nor do I want to overcomplicate a solution so much: classes, OOP, inheritance, mapping... I don't need any of this. I need only a simple algorithm in Python, C or pseudo-code Jun 13, 2021 at 12:20
• Also, the amount of attributes and the values of each attribute comes at runtime, from a user Jun 13, 2021 at 12:21