This feels like it should be easier than it is but if I have values A B C I could have

A A A

A A B

e.t.c

A C B

C C A

e.t.c.

Is there a simple way of computing them in say c#, javascript, python or psuedo code? I basically want a 2d array with all combinations in one dimension and the values in another.

CodePudding user response：

All the ways you count N digits is really each digit prepended to all the ways you count N-1 digits. All the ways you count 1 digit, is just all the digits.

With that...

function nCombosOfABC(nDigits) {
  if (nDigits === 1) return ['A', 'B', 'C']
  let result = []
  let n1 = nCombosOfABC(nDigits-1)
  for (let r of n1) {
    for (let letter of ['A', 'B', 'C']) {
      result.push([letter, ...r])
    }
  }
  return result
}

console.log(nCombosOfABC(3))

CodePudding user response：

So this is a crude solution for those that want to know? The point of this was to generate every combination of kernel of size and categories combination.

public static float[][] GenerateCombinations(int size, float[] categories)
    {
        List<float[]> combinations = new List<float[]>();
        var totalKernels = (int)Math.Pow(categories.Length, size);
        var currentIndexes = new int[size];

        var firstOutput = new float[size];
        combinations.Add(firstOutput);

        for (var i = 1; i < totalKernels; i  )
        {
            Console.Write("\n");
            var output = new float[size];
            var carry = 0;

            for (var j = 0; j < size; j  )
            {
                if (j == 0)
                {
                    currentIndexes[j]  ;
                }
                if (carry != 0)
                {
                    currentIndexes[j]  = carry;
                    carry = 0;
                }
                if (currentIndexes[j] >= categories.Length)
                {
                    carry = 1;
                    output[j] = categories[0];
                    currentIndexes[j] = 0;
                }
                else
                {
                    output[j] = categories[currentIndexes[j]];
                }
                Console.Write($" {output[j]}");
            }
            combinations.Add(output);
        }
        return combinations.ToArray();
    }

CodePudding user response：

Here are a few different approaches in python

Triple nested loop

We find all possible triplets by iterating on all possible values of the first element, and iterating on all possible values of the second element, and iterating on all possible values of the third element.

• Pros: extremely simple to understand and code;
• Cons: the number of elements per tuple is hard-coded; we'd need a different function if we wanted pairs or quadruplets or quintuplets instead of triplets.

def all_triplets(seq):
    for x in seq:
        for y in seq:
            for z in seq:
                yield (x,y,z)

print(list(all_triplets('AB')))
# [('A', 'A', 'A'), ('A', 'A', 'B'), ('A', 'B', 'A'), ('A', 'B', 'B'), ('B', 'A', 'A'), ('B', 'A', 'B'), ('B', 'B', 'A'), ('B', 'B', 'B')]

print(list(all_triplets('ABC')))
# [('A', 'A', 'A'), ('A', 'A', 'B'), ('A', 'A', 'C'), ('A', 'B', 'A'), ('A', 'B', 'B'), ('A', 'B', 'C'), ('A', 'C', 'A'), ('A', 'C', 'B'), ('A', 'C', 'C'), ('B', 'A', 'A'), ('B', 'A', 'B'), ('B', 'A', 'C'), ('B', 'B', 'A'), ('B', 'B', 'B'), ('B', 'B', 'C'), ('B', 'C', 'A'), ('B', 'C', 'B'), ('B', 'C', 'C'), ('C', 'A', 'A'), ('C', 'A', 'B'), ('C', 'A', 'C'), ('C', 'B', 'A'), ('C', 'B', 'B'), ('C', 'B', 'C'), ('C', 'C', 'A'), ('C', 'C', 'B'), ('C', 'C', 'C')]

Recurrence relation

Instead of nested loops, we use a recurrence relation for Cartesian product:

product(seq with itself n times) == product(seq, product(seq with itself n-1 times))

We will still iterate on all possible values of the first element; but instead of using hard-coded nested loops to iterate on all possible values of the remaining elements, we will use the recurrence relation to get the possible values of the remaining elements.

Like all recurrence relations, it can easily be used to write either an iterative function or a recursive function. Since python is pretty terrible when it comes to recursion, here is an iterative version.

• Pros: the number of elements per tuple is now a parameter;
• Cons: this is harder to understand than the hard-coded nested loop.

def all_n_uplets(seq, n):
    '''assume n >= 1'''
    result = seq
    for _ in range(n-1):
        result = [ (x, *t) for x in seq for t in result ]
    return result

print(all_n_uplets('ABC', 2))
# [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]

print(all_n_uplets('ABC', 3))
# [('A', 'A', 'A'), ('A', 'A', 'B'), ('A', 'A', 'C'), ('A', 'B', 'A'), ('A', 'B', 'B'), ('A', 'B', 'C'), ('A', 'C', 'A'), ('A', 'C', 'B'), ('A', 'C', 'C'), ('B', 'A', 'A'), ('B', 'A', 'B'), ('B', 'A', 'C'), ('B', 'B', 'A'), ('B', 'B', 'B'), ('B', 'B', 'C'), ('B', 'C', 'A'), ('B', 'C', 'B'), ('B', 'C', 'C'), ('C', 'A', 'A'), ('C', 'A', 'B'), ('C', 'A', 'C'), ('C', 'B', 'A'), ('C', 'B', 'B'), ('C', 'B', 'C'), ('C', 'C', 'A'), ('C', 'C', 'B'), ('C', 'C', 'C')]

Standard library

Cartesian product is already implemented in python: it's function product in module itertools. It can be used to compute the Cartesian product of several different sequences, or of a sequence with itself.

• Pros: it's already there, no need to reimplement the wheel;
• Cons: the name itertools.product is specific to python, if you want to use another language, you'll need to look for the equivalent.

from itertools import product

print(list(product('ABC', repeat=3)))
# [('A', 'A', 'A'), ('A', 'A', 'B'), ('A', 'A', 'C'), ('A', 'B', 'A'), ('A', 'B', 'B'), ('A', 'B', 'C'), ('A', 'C', 'A'), ('A', 'C', 'B'), ('A', 'C', 'C'), ('B', 'A', 'A'), ('B', 'A', 'B'), ('B', 'A', 'C'), ('B', 'B', 'A'), ('B', 'B', 'B'), ('B', 'B', 'C'), ('B', 'C', 'A'), ('B', 'C', 'B'), ('B', 'C', 'C'), ('C', 'A', 'A'), ('C', 'A', 'B'), ('C', 'A', 'C'), ('C', 'B', 'A'), ('C', 'B', 'B'), ('C', 'B', 'C'), ('C', 'C', 'A'), ('C', 'C', 'B'), ('C', 'C', 'C')]

print(list(product('ABC', 'ABC', 'ABC')))
# [('A', 'A', 'A'), ('A', 'A', 'B'), ('A', 'A', 'C'), ('A', 'B', 'A'), ('A', 'B', 'B'), ('A', 'B', 'C'), ('A', 'C', 'A'), ('A', 'C', 'B'), ('A', 'C', 'C'), ('B', 'A', 'A'), ('B', 'A', 'B'), ('B', 'A', 'C'), ('B', 'B', 'A'), ('B', 'B', 'B'), ('B', 'B', 'C'), ('B', 'C', 'A'), ('B', 'C', 'B'), ('B', 'C', 'C'), ('C', 'A', 'A'), ('C', 'A', 'B'), ('C', 'A', 'C'), ('C', 'B', 'A'), ('C', 'B', 'B'), ('C', 'B', 'C'), ('C', 'C', 'A'), ('C', 'C', 'B'), ('C', 'C', 'C')]

Note that searching for library functions forces you to adopt vocabulary that is consistent with the vocabulary used by the community. Make a distinction between the following concepts:

• Cartesian product, or "combinations with replacement";
• powerset, or "set of all subsets";
• permutations;
• combinations (without replacement);
• derangements;
• distinct permutations (for a sequence with duplicates);
• etc.