Algorithme permettant de retourner toutes les combinaisons de k éléments parmi n

Question

Je veux écrire une fonction qui prend un tableau de lettres comme argument et un nombre de ces lettres à sélectionner.

Disons que vous fournissez un tableau de 8 lettres et que vous voulez en sélectionner 3. Alors vous devriez obtenir :

8! / ((8 - 3)! * 3!) = 56

Des tableaux (ou mots) en retour composés de 3 lettres chacun.

Answer 1

Il n'y a pas besoin de manipulations de collecte. Le problème est presque le même que celui du passage en revue de K boucles imbriquées, mais il faut faire attention aux index et aux limites (en ignorant les trucs de Java et de la POO) :

 public class CombinationsGen {
    private final int n;
    private final int k;
    private int[] buf;

    public CombinationsGen(int n, int k) {
        this.n = n;
        this.k = k;
    }

    public void combine(Consumer<int[]> consumer) {
        buf = new int[k];
        rec(0, 0, consumer);
    }

    private void rec(int index, int next, Consumer<int[]> consumer) {
        int max = n - index;

        if (index == k - 1) {
            for (int i = 0; i < max && next < n; i++) {
                buf[index] = next;
                next++;
                consumer.accept(buf);
            }
        } else {
            for (int i = 0; i < max && next + index < n; i++) {
                buf[index] = next;
                next++;
                rec(index + 1, next, consumer);
            }
        }
    }
}

Utilisez comme ça :

 CombinationsGen gen = new CombinationsGen(5, 2);

 AtomicInteger total = new AtomicInteger();
 gen.combine(arr -> {
     System.out.println(Arrays.toString(arr));
     total.incrementAndGet();
 });
 System.out.println(total);

Obtenez les résultats escomptés :

[0, 1]
[0, 2]
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
10

Enfin, faites correspondre les index à tout ensemble de données dont vous disposez.

Answer 2

Algorithme de backtracking C++ simple mais lent.

#include <iostream>

void backtrack(int* numbers, int n, int k, int i, int s)
{
    if (i == k)
    {
        for (int j = 0; j < k; ++j)
        {
            std::cout << numbers[j];
        }
        std::cout << std::endl;

        return;
    }

    if (s > n)
    {
        return;
    }

    numbers[i] = s;
    backtrack(numbers, n, k, i + 1, s + 1);
    backtrack(numbers, n, k, i, s + 1);
}

int main(int argc, char* argv[])
{
    int n = 5;
    int k = 3;

    int* numbers = new int[k];

    backtrack(numbers, n, k, 0, 1);

    delete[] numbers;

    return 0;
}

Answer 3

J'ai créé une classe générale pour les combinaisons en C++. Elle est utilisée comme ceci.

char ar[] = "0ABCDEFGH";
nCr ncr(8, 3);
while(ncr.next()) {
    for(int i=0; i<ncr.size(); i++) cout << ar[ncr[i]];
    cout << ' ';
}

Ma bibliothèque ncr[i] retourne à partir de 1, pas à partir de 0. C'est pourquoi il y a 0 dans le tableau. Si vous voulez considérer l'ordre, changez simplement la classe nCr en nPr. L'utilisation est identique.

Résultat

ABC ABD ABE ABF ABG ABH ACD ACE ACF ACG ACH ADE ADF ADG ADH AEF AEG AEH AFG AFH AGH BCD BCE BCF BCG BCH BDE BDF BDG BDH BEF BEG BEH BFG BFH BGH CDE CDF CDG CDH CEF CEG CEH CFG CFH CGH DEF DEG DEH DFG DFH DGH EFG EFH EGH FGH

Voici le fichier d'en-tête.

#pragma once
#include <exception>

class NRexception : public std::exception
{
public:
    virtual const char* what() const throw() {
        return "Combination : N, R should be positive integer!!";
    }
};

class Combination
{
public:
    Combination(int n, int r);
    virtual ~Combination() { delete [] ar;}
    int& operator[](unsigned i) {return ar[i];}
    bool next();
    int size() {return r;}
    static int factorial(int n);

protected:
    int* ar;
    int n, r;
};

class nCr : public Combination
{
public: 
    nCr(int n, int r);
    bool next();
    int count() const;
};

class nTr : public Combination
{
public:
    nTr(int n, int r);
    bool next();
    int count() const;
};

class nHr : public nTr
{
public:
    nHr(int n, int r) : nTr(n,r) {}
    bool next();
    int count() const;
};

class nPr : public Combination
{
public:
    nPr(int n, int r);
    virtual ~nPr() {delete [] on;}
    bool next();
    void rewind();
    int count() const;

private:
    bool* on;
    void inc_ar(int i);
};

Et la mise en œuvre.

#include "combi.h"
#include <set>
#include<cmath>

Combination::Combination(int n, int r)
{
    //if(n < 1 || r < 1) throw NRexception();
    ar = new int[r];
    this->n = n;
    this->r = r;
}

int Combination::factorial(int n) 
{
    return n == 1 ? n : n * factorial(n-1);
}

int nPr::count() const
{
    return factorial(n)/factorial(n-r);
}

int nCr::count() const
{
    return factorial(n)/factorial(n-r)/factorial(r);
}

int nTr::count() const
{
    return pow(n, r);
}

int nHr::count() const
{
    return factorial(n+r-1)/factorial(n-1)/factorial(r);
}

nCr::nCr(int n, int r) : Combination(n, r)
{
    if(r == 0) return;
    for(int i=0; i<r-1; i++) ar[i] = i + 1;
    ar[r-1] = r-1;
}

nTr::nTr(int n, int r) : Combination(n, r)
{
    for(int i=0; i<r-1; i++) ar[i] = 1;
    ar[r-1] = 0;
}

bool nCr::next()
{
    if(r == 0) return false;
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n-r+2+i) {
        if(--i == -1) return false;
        ar[i]++;
    }
    while(i < r-1) ar[i+1] = ar[i++] + 1;
    return true;
}

bool nTr::next()
{
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n+1) {
        ar[i] = 1;
        if(--i == -1) return false;
        ar[i]++;
    }
    return true;
}

bool nHr::next()
{
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n+1) {
        if(--i == -1) return false;
        ar[i]++;
    }
    while(i < r-1) ar[i+1] = ar[i++];
    return true;
}

nPr::nPr(int n, int r) : Combination(n, r)
{
    on = new bool[n+2];
    for(int i=0; i<n+2; i++) on[i] = false;
    for(int i=0; i<r; i++) {
        ar[i] = i + 1;
        on[i] = true;
    }
    ar[r-1] = 0;
}

void nPr::rewind()
{
    for(int i=0; i<r; i++) {
        ar[i] = i + 1;
        on[i] = true;
    }
    ar[r-1] = 0;
}

bool nPr::next()
{   
    inc_ar(r-1);

    int i = r-1;
    while(ar[i] == n+1) {
        if(--i == -1) return false;
        inc_ar(i);
    }
    while(i < r-1) {
        ar[++i] = 0;
        inc_ar(i);
    }
    return true;
}

void nPr::inc_ar(int i)
{
    on[ar[i]] = false;
    while(on[++ar[i]]);
    if(ar[i] != n+1) on[ar[i]] = true;
}

Answer 4

Combinaisons très rapides pour MetaTrader MQL4 implémentées comme objet itérateur.

Le code est si simple à comprendre.

J'ai évalué de nombreux algorithmes, celui-ci est vraiment très rapide - environ 3x plus rapide que la plupart des fonctions next_combination().

class CombinationsIterator
{
private:
    int input_array[];  // 1 2 3 4 5
    int index_array[];  // i j k
    int m_elements;     // N
    int m_indices;      // K

public:
    CombinationsIterator(int &src_data[], int k)
    {
        m_indices = k;
        m_elements = ArraySize(src_data);
        ArrayCopy(input_array, src_data);
        ArrayResize(index_array, m_indices);

        // create initial combination (0..k-1)
        for (int i = 0; i < m_indices; i++)
        {
            index_array[i] = i;
        }
    }

    // https://stackoverflow.com/questions/5076695
    // bool next_combination(int &item[], int k, int N)
    bool advance()
    {
        int N = m_elements;
        for (int i = m_indices - 1; i >= 0; --i)
        {
            if (index_array[i] < --N)
            {
                ++index_array[i];
                for (int j = i + 1; j < m_indices; ++j)
                {
                    index_array[j] = index_array[j - 1] + 1;
                }
                return true;
            }
        }
        return false;
    }

    void getItems(int &items[])
    {
        // fill items[] from input array
        for (int i = 0; i < m_indices; i++)
        {
            items[i] = input_array[index_array[i]];
        }
    }
};

Un programme pilote pour tester la classe d'itérateurs ci-dessus :

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
// driver program to test above class

#define N 5
#define K 3

void OnStart()
{
    int myset[N] = {1, 2, 3, 4, 5};
    int items[K];

    CombinationsIterator comboIt(myset, K);

    do
    {
        comboIt.getItems(items);

        printf("%s", ArrayToString(items));

    } while (comboIt.advance());

}

Output:
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5

Answer 5

Voici une solution JS simple :

function getAllCombinations(n, k, f1) {
    indexes = Array(k);
  for (let i =0; i< k; i++) {
    indexes[i] = i;
  }
  var total = 1;
  f1(indexes);
  while (indexes[0] !== n-k) {
    total++;
        getNext(n, indexes);
    f1(indexes);
  }
  return {total};
}

function getNext(n, vec) {
    const k = vec.length;
  vec[k-1]++;
    for (var i=0; i<k; i++) {
    var currentIndex = k-i-1;
    if (vec[currentIndex] === n - i) {
        var nextIndex = k-i-2;
      vec[nextIndex]++;
      vec[currentIndex] = vec[nextIndex] + 1;
    }
  }

    for (var i=1; i<k; i++) {
    if (vec[i] === n - (k-i - 1)) {
      vec[i] = vec[i-1] + 1;
    }
  }
    return vec;
} 

let start = new Date();
let result = getAllCombinations(10, 3, indexes => console.log(indexes)); 
let runTime = new Date() - start; 

console.log({
result, runTime
});