combinatorics – All possible combinations of a one-dimensional array

Question:

Friends, tell me in theory what are the practices for the approach to calculating the number of possible combinations from the elements of a one-dimensional array. And iterate over all possible sequences.

For example, there are elements 2,45,16,34 – how do you know the possible combinations? (I'm not asking for a code, I'm asking for a theory)

Answer:

Permutations

Permutations are combinations of the original array obtained by permuting elements. Number of permutations An = n! The algorithm for obtaining a permutation by number (1..n!) Is as follows:

var facts = [];
function fact(N){
    if(N==0 || N==1) return 1;
    if(facts[N]) return facts[N];
    facts[N] = N*fact(N-1);
    return facts[N];
}
function permutation(index, A){
    var n=A.length;
    var i=index+1;
    var res=[];
    for(var t=1;t<=n;t++){
        var f = fact(n-t);
        var k=Math.floor((i+f-1)/f);
        res.push(A.splice(k-1,1)[0]);
        i-=(k-1)*f;
    }
    if (A.length) res.push(A[0]);
    return res;
}

function log(){
  var msg = Array.prototype.slice.call(arguments).join(" ");
  document.getElementById("log").value+="\n"+msg;
  console.log(arguments);
}
var M = ["A","B","C","D","E"];
for(var i=0;i<fact(M.length);i++){
    log(i,permutation(i,M.slice(0)).join(""));
}
html, body {margin:0;padding:0;height:100%}
#log {width:100%;height:100%;border:0;padding:0;display:block}
<textarea id="log"></textarea>

The point is that at each iteration we take an element from the array and remove it, moving on to the next iteration, we have an array of smaller length … and so we continue until the original array is empty. In this case, the combination number is obtained based on the order of taking out the array elements. A similar approach is used in the Fisher – Yates algorithm for shuffling an array, only there the element that will be selected at each iteration is taken randomly.

Combinations

Combinations are sets of a certain length (k) made up of a set of a certain length (n). Combinations in which the same elements are reversed are considered one combination, therefore, for convenience, those combinations are taken in which the elements are sorted in ascending order (in lexicographic order). The number of combinations C (n, k) – read as "Tse from en po ka", = n! / (K! (Nk)!), Are called binomial coefficients. The algorithm for obtaining a combination by number is as follows:

var facts = [];

function fact(N) {
  if (N == 0 || N == 1) return 1;
  if (facts[N]) return facts[N];
  facts[N] = N * fact(N - 1);
  return facts[N];
}

function C(n, k) {
  return fact(n) / fact(k) / fact(n - k);
}

function combination(index, k, A) {
  var res = [0];
  var n = A.length;
  var s = 0;
  for (var t = 1; t <= k; t++) {
    var j = res[t - 1] + 1;
    while ((j < (n - k + t)) && ((s + C(n - j, k - t)) <= index)) {
      s += C(n - j, k - t);
      j++;
    }
    res.push(j);
  }
  res.splice(0, 1);
  return res;
}

function log() {
  var msg = Array.prototype.slice.call(arguments).join(" ");
  document.getElementById("log").value += "\n" + msg;
  console.log(arguments);
}
var M = ["A", "B", "C", "D", "E"];
for (var i = 0; i < C(M.length, 3); i++) {
  log(i, combination(i, 3, M.slice(0)).join(""));
}
html,
body {
  margin: 0;
  padding: 0;
  height: 100%
}
#log {
  width: 100%;
  height: 100%;
  border: 0;
  padding: 0;
  display: block
}
<textarea id="log"></textarea>

The combination number is taken as the sum of all binomial coefficients for arrays of decreasing length (in fact, it is difficult to formulate the principle of numbering briefly and, moreover, it is clear, the link to the theory will be below).

Accommodation

Combinations and permutations are special cases of placements . Placements are combinations where the order of elements is important. Or, in other words, these are permutations of combinations. Number of placements A (n, k) = k! * C (n, k) = n! / (Nk) !. Thus, in order to get the placement by number, we divide the total number of placements by an integer by the number – we get the number of the combination, and apply to it the permutation with the number as the remainder of dividing the number of placements by the placement number.

Placements with repetitions

A separate variation of the combination is placement with repetition . A '(n, k) = n ^ k. Those. all variants of arrays of length k, where at each position there can be any element from a set of size n. The easiest option to understand is A (10, k) – all decimal numbers from 0 to 10 ^ k-1. Or A (2, k) – all binary numbers of length k.
The numbering of elements is natural, the index of the combination corresponds to the decimal analogue of the number in the n-ary number system.

see also

You can read about the numbering of placements and combinations in the article "On the numbering of permutations and combinations for organizing parallel computations in control system design problems" (googled), the algorithms are given from there, links in the article lead to:

  • Dijkstra E. Programming discipline.
  • Lipsky V. Combinatorics for programmers.

Optimization

Since the calculations are carried out using factorials, long arithmetic is most likely required for large values ​​of n, k. At the same time, it is quite possible that the exact calculation of the factorial is not needed (it is necessary to check), and the Stirling formula will suffice … In the above algorithms, the factorial function is written for ease of understanding.

Inverse problem

Each of the combinations can have an inverse problem – getting a number by combination. Having an idea of ​​the numbering principle, the inverse problem is also solved. For example, for placements with repetitions, this is the translation of the n-ary number system to decimal …

Usage

Having calculated values ​​of factorials or, in general, tables with all combinations of a certain type, it is possible to obtain a random combination using only one RNG call to obtain a combination.

Scroll to Top