# Ordered Cartesian Product

Say I have three sets:

A = [banana, apple, grape]

B = [1, 2, 3, 4]

C = [Alice, Bob, Carol]


I need to design an algorithm that gives me the Cartesian Product A x B x C, but with any number of sets and any number of elements in each set. Another requirement is that the order of the elements in the Product is such:

A x B x C = [(banana, 1, Alice),
(apple, 1, Alice),
(banana, 2, Alice),
(banana, 1, Bob),
...]


I could only come up with a recursive algorithm that ends up giving me:

A x B x C = [(banana, 1, Alice),
(banana, 1, Bob),
(banana, 1, Carol),
(banana, 2, Alice),
...]


Obviously, A x B x C needs to have every possible combination of the elements of the sets. Also, I need an algorithm that covers the general case of any number of sets, not only three. Is there any well-known algorithm that provides the Cartesian Product in this order that I need?

Any help or tips is much appreciated.

• It looks like the loops order is sufficient to reproduce your order. What have you tried? Why do you need special algorithm for that? – Evil Jan 3 '18 at 1:47
• I've tried doing it recursively, something like this approach: stackoverflow.com/questions/10262215/… I need this algorithm to give me the highest entropy combinations of the elements in the initial sets, in descending order... The sets are ordered in terms of frequency of occurance of each element, in descending order – Bernardo Rodrigues Jan 3 '18 at 15:09

You want to enumerate first by sum, then by lexicographic order of some sort (it's impossible to tell which type exactly from your example). Replacing actual elements with indices, here is the order you're interested in for $A \times B$: $$(0,0) \\ (1,0), (0,1) \\ (2,0), (1,1), (0,2) \\ \ldots$$ It's a simple exercise to generate this order for $A \times B$. Generating the order for $A \times B$ is somewhat more challenging, but still not too bad. When generating the triples summing to $n$, if we focus on just the first two parts of each pair, then we're interested in a list of all pairs $(i,j)$ such that $i+j \leq n$, in some sort of lexicographic order. Whichever variant of the lexicographic order you choose, you should be able to figure out how to generate it by looking at some examples.

• I think your answer is good and points in the right direction, but I still can't see how this would work in a more general scenario, which is what I need... like A x B x C x D x ... – Bernardo Rodrigues Jan 5 '18 at 17:34

If anyone is interested, I was finally able to figure this out. Many thanks to Yuval Filmus for his answer, without it I wouldn't be able to achieve this!

This is my code in Go. Most variables and comments are in portuguese (sorry!), and organization is not perfect, but works!

package main

import (
"fmt"
)

func main() {

// inicializa os arrays
var frutas = []string{"banana", "maçã", "uva"}
var nums = []string{"1", "2", "3", "4"}
var nomes = []string{"wesley", "rodrigo", "igor", "regina", "marcos", "bernardo"}

arrays := [][]string{frutas, nums, nomes}

for n := 0; n < nMax; n++{

for k := 0; k < l; k++{

palpite := ""
for i, indice := range indices{
palpite += arrays[i][indice]
}
fmt.Println(palpite)
}
}
}

nMax := 0
tamanhos := make([]int, 0)
for _, array := range arrays{
nMax += len(array) - 1
tamanhos = append(tamanhos, len(array))
}
nMax++

// inicializa canal com arrays do produto cartesiano dos indices
produtoCartesiano := produtoCartesiano(tamanhos)

// inicializa saida
saida := make([][][]int, nMax)

for elemento := range produtoCartesiano{
soma := 0
for _, i := range elemento{
soma += i
}

saida[soma] = append(saida[soma], elemento)
}

return nMax, saida
}

// gera canal com arrays do produto cartesiano dos indices
func produtoCartesiano(tamanhos []int) chan []int{
// inicializa canal de saída
saida := make(chan []int)

// lança gorrotina recursiva
go recursao(tamanhos, nil, 0, saida)

// retorna canal de saída
return saida
}

// lança os valores do produto cartesiano dos arrays no canal de saída
pMax := len(tamanhos)

// primeiro nível de recursão... inicializa contadores e tamanhos

}

// último nível de profundidade na recursão

for p := 0; p < pMax; p++{
}

// envia elemento no canal de saída

// qualquer outra profundidade que não seja a última
}else{
// varre array da profundidade atual
}
}

// hora de fechar canal?
// analisa contadores de todos arrays... se todos forem iguais aos respectivos tamanhos,
// então todos elementos do produto cartesiano foram calculados, e o canal pode ser fechado
fecha := true
for i := 0; i < pMax; i++{
fecha = false
}
}

// fecha canal
if fecha{
close(saida)
}
}


This is the output, which is exactly what I needed:

banana1wesley
banana1rodrigo
banana2wesley
maçã1wesley
banana1igor
banana2rodrigo
banana3wesley
maçã1rodrigo
maçã2wesley
uva1wesley
banana1regina
banana2igor
banana3rodrigo
banana4wesley
maçã1igor
maçã2rodrigo
maçã3wesley
uva1rodrigo
uva2wesley
banana1marcos
banana2regina
banana3igor
banana4rodrigo
maçã1regina
maçã2igor
maçã3rodrigo
maçã4wesley
uva1igor
uva2rodrigo
uva3wesley
banana1bernardo
banana2marcos
banana3regina
banana4igor
maçã1marcos
maçã2regina
maçã3igor
maçã4rodrigo
uva1regina
uva2igor
uva3rodrigo
uva4wesley
banana2bernardo
banana3marcos
banana4regina
maçã1bernardo
maçã2marcos
maçã3regina
maçã4igor
uva1marcos
uva2regina
uva3igor
uva4rodrigo
banana3bernardo
banana4marcos
maçã2bernardo
maçã3marcos
maçã4regina
uva1bernardo
uva2marcos
uva3regina
uva4igor
banana4bernardo
maçã3bernardo
maçã4marcos
uva2bernardo
uva3marcos
uva4regina
maçã4bernardo
uva3bernardo
uva4marcos
uva4bernardo