All possible combinations of a one-dimensional array

Permutations

Permutations are combinations of the original array obtained by permuting elements. Number of permutations An = n! Algorithm for obtaining a permutation by number (1..n!) such is:

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 meaning 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 shorter length... and so we continue until the original array is empty. At the same time, the number combinations are obtained based on the order in which the array elements are taken out. A similar approach is used in the Fisher–Yates algorithm to shuffle 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) composed of a set of a certain length (n). Combinations in which the same elements are swapped are considered one combination, so for for convenience, we take those combinations in which the elements are ordered in ascending order (in lexicographic order). The number of combinations C (n, k)-read as "Tse from en to ka", = n!/(k!(n-k)!), are called binomial coefficients. The algorithm for getting 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, to formulate the principle briefly and clearly numbering is difficult, the link to the theory will be below).

Placements

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

Placements with repetitions

A separate variant of the combination is placement with repetition. A'(n,k) = n^k. That is, all variants of arrays of length k, where at each position there can be any element from the 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 the elements is natural, the index of the combination corresponds to the decimal equivalent of a number in the n-ric 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 computing in control system design problems" (Googled), the algorithms are given from there, the links in the article lead to:

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

Optimization

Since the calculations are performed using factorials, then for large values of n,k, most likely, long arithmetic may be required. At the same time, it is quite possible that the exact calculation of the factorial will not be necessary (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 possible combinations can have the 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 a translation of the n-ric number system into decimal...

Using

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

I don't know how this is done in php, but in theory, you can use the following algorithm:

Iterate through all the numbers from 0 (no elements) to (2^n) - 1( all elements), where n is the length of the array.

At each step of the iteration, we look at all the bits of the number, and if the i-th bit is equal to one, then the i-th element will be included in the combination.

For example, for three elements:

• 0 - no elements
• 1 - (001) only the 1st element
• 2 - (010) only 2nd
• 3 - (011) 2nd and 1st
• 4 - (100) only 3rd
• 5 - (101) 1st and 3rd
• 6 - (110) 1st and 2nd
• 7 - (111) 1st, 2nd, 3rd

    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 = ["п","о","б","а","е","с","п","р","о","с","и","у"];
for(var i=0;i<fact(M.length);i++){
    log(i,permutation(i,M.slice(0)).join(""));
}