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

Voici ma contribution en javascript (sans récursion)

set = ["q0", "q1", "q2", "q3"]
collector = []

function comb(num) {
  results = []
  one_comb = []
  for (i = set.length - 1; i >= 0; --i) {
    tmp = Math.pow(2, i)
    quotient = parseInt(num / tmp)
    results.push(quotient)
    num = num % tmp
  }
  k = 0
  for (i = 0; i < results.length; ++i)
    if (results[i]) {
      ++k
      one_comb.push(set[i])
    }
  if (collector[k] == undefined)
    collector[k] = []
  collector[k].push(one_comb)
}

sum = 0
for (i = 0; i < set.length; ++i)
  sum += Math.pow(2, i)
 for (ii = sum; ii > 0; --ii)
  comb(ii)
 cnt = 0
for (i = 1; i < collector.length; ++i) {
  n = 0
  for (j = 0; j < collector[i].length; ++j)
    document.write(++cnt, " - " + (++n) + " - ", collector[i][j], "<br>")
  document.write("<hr>")
}

Answer 2

Que diriez-vous de cette réponse ... qui imprime toutes les combinaisons de longueur 3 ... et qui peut être généralisée pour toute longueur ... Code de travail ...

#include<iostream>
#include<string>
using namespace std;

void combination(string a,string dest){
int l = dest.length();
if(a.empty() && l  == 3 ){
 cout<<dest<<endl;}
else{
  if(!a.empty() && dest.length() < 3 ){
     combination(a.substr(1,a.length()),dest+a[0]);}
  if(!a.empty() && dest.length() <= 3 ){
      combination(a.substr(1,a.length()),dest);}
 }

 }

 int main(){
 string demo("abcd");
 combination(demo,"");
 return 0;
 }

Answer 3

Encore une autre solution récursive (vous devriez pouvoir la porter pour utiliser des lettres au lieu de chiffres) utilisant une pile, un peu plus courte que la plupart cependant :

stack = [] 
def choose(n,x):
   r(0,0,n+1,x)

def r(p, c, n,x):
   if x-c == 0:
      print stack
      return

   for i in range(p, n-(x-1)+c):
      stack.append(i)
      r(i+1,c+1,n,x)
      stack.pop()

4 choisissez 3 ou je veux les 3 combinaisons de chiffres de 0 à 4.

choose(4,3) 

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

Answer 4

Voici une implémentation de coffeescript

combinations: (list, n) ->
        permuations = Math.pow(2, list.length) - 1
        out = []
        combinations = []

        while permuations
            out = []

            for i in [0..list.length]
                y = ( 1 << i )
                if( y & permuations and (y isnt permuations))
                    out.push(list[i])

            if out.length <= n and out.length > 0
                combinations.push(out)

            permuations--

        return combinations

Answer 5

Peut-être n'ai-je pas compris (que vous avez besoin de l'algorithme et non d'une solution toute faite), mais il semble que Scala le fasse d'emblée (maintenant) :

def combis(str:String, k:Int):Array[String] = {
  str.combinations(k).toArray 
}

En utilisant la méthode comme ceci :

  println(combis("abcd",2).toList)

Produira :

  List(ab, ac, ad, bc, bd, cd)