Algoritma untuk mengembalikan semua kombinasi elemen k dari n

Saya ingin menulis fungsi yang mengambil array huruf sebagai argumen dan sejumlah huruf untuk memilih.

Katakanlah Anda memberikan array 8 huruf dan ingin memilih 3 huruf dari itu. Maka Anda harus mendapatkan:

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

Array (atau kata-kata) sebagai imbalannya masing-masing terdiri dari 3 huruf.

Seni Pemrograman Komputer Volume 4: Fascicle 3 memiliki banyak ini yang mungkin cocok dengan situasi khusus Anda lebih baik daripada cara saya menggambarkan.

Kode Abu-abu

Masalah yang akan Anda temui tentu saja adalah memori dan cukup cepat, Anda akan memiliki masalah dengan 20 elemen di set Anda - ²⁰ C ₃ = 1140. Dan jika Anda ingin beralih di set, yang terbaik adalah menggunakan abu-abu yang dimodifikasi algoritma kode sehingga Anda tidak menyimpan semuanya dalam memori. Ini menghasilkan kombinasi berikutnya dari sebelumnya dan menghindari pengulangan. Ada banyak dari ini untuk kegunaan yang berbeda. Apakah kita ingin memaksimalkan perbedaan antara kombinasi yang berurutan? memperkecil? dan lain-lain.

Beberapa makalah asli yang menggambarkan kode abu-abu:

1. Beberapa Jalur Hamilton dan Algoritma Perubahan Minimal
2. Algoritma Generasi Kombinasi Pertukaran Bersebelahan

Berikut adalah beberapa makalah lain yang membahas topik ini:

1. Implementasi Efisien dari Eades, Cupang, Baca Algoritma Generasi Kombinasi Interchange Berdampingan (PDF, dengan kode dalam Pascal)
2. Generator Kombinasi
3. Survei Kode Kelabu Kombinatorial (PostScript)
4. Algoritma untuk Kode Gray

Chase's Twiddle (algoritme)

Phillip J Chase, ` Algoritma 382: Kombinasi M out of N Objects '(1970)

Algoritme dalam C ...

Indeks Kombinasi dalam Urutan Leksikografis (Algoritma Buckles 515)

Anda juga dapat mereferensikan kombinasi berdasarkan indeksnya (dalam urutan leksikografis). Menyadari bahwa indeks harus berupa sejumlah perubahan dari kanan ke kiri berdasarkan indeks, kita dapat membuat sesuatu yang harus memulihkan kombinasi.

Jadi, kami memiliki satu set {1,2,3,4,5,6} ... dan kami ingin tiga elemen. Katakanlah {1,2,3} kita dapat mengatakan bahwa perbedaan antara elemen adalah satu dan dalam urutan dan minimal. {1,2,4} memiliki satu perubahan dan secara leksikografis nomor 2. Jadi jumlah 'perubahan' di tempat terakhir menyumbang satu perubahan dalam pemesanan leksikografis. Tempat kedua, dengan satu perubahan {1,3,4} memiliki satu perubahan tetapi menyumbang lebih banyak perubahan karena berada di tempat kedua (sebanding dengan jumlah elemen dalam set asli).

Metode yang saya jelaskan adalah dekonstruksi, seperti yang terlihat, dari set ke indeks, kita perlu melakukan sebaliknya - yang jauh lebih rumit. Inilah cara Buckles memecahkan masalah. Saya menulis beberapa C untuk menghitungnya , dengan perubahan kecil - Saya menggunakan indeks set daripada rentang angka untuk mewakili set, jadi kami selalu bekerja dari 0 ... n. catatan:

1. Karena kombinasi tidak berurutan, {1,3,2} = {1,2,3} --kami memesannya harus leksikografis.
2. Metode ini memiliki 0 implisit untuk memulai set untuk perbedaan pertama.

Indeks Kombinasi dalam Urutan Leksikografis (McCaffrey)

Ada cara lain : konsepnya lebih mudah dipahami dan diprogram tetapi tanpa optimalisasi Buckles. Untungnya, itu juga tidak menghasilkan kombinasi duplikat:

Himpunan yang memaksimalkan , di mana .

Untuk contoh: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). Jadi, kombinasi leksikografis ke-27 dari empat hal adalah: {1,2,5,6}, itu adalah indeks dari set apa pun yang ingin Anda lihat. Contoh di bawah ini (OCaml), memerlukan choosefungsi, diserahkan kepada pembaca:

(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
    (* maximize function -- maximize a that is aCb              *)
    (* return largest c where c < i and choose(c,i) <= z        *)
    let rec maximize a b x =
        if (choose a b ) <= x then a else maximize (a-1) b x
    in
    let rec iterate n x i = match i with
        | 0 -> []
        | i ->
            let max = maximize n i x in
            max :: iterate n (x - (choose max i)) (i-1)
    in
    if x < 0 then failwith "errors" else
    let idxs =  iterate (List.length set) x k in
    List.map (List.nth set) (List.sort (-) idxs)

Iterator kombinasi kecil dan sederhana

Dua algoritma berikut disediakan untuk tujuan didaktik. Mereka menerapkan iterator dan (secara keseluruhan) folder kombinasi keseluruhan. Mereka adalah secepat mungkin, memiliki kompleksitas O ( ⁿ C _k ). Konsumsi memori terikat oleh k.

Kami akan mulai dengan iterator, yang akan memanggil fungsi yang disediakan pengguna untuk setiap kombinasi

let iter_combs n k f =
  let rec iter v s j =
    if j = k then f v
    else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
  iter [] 0 0

Versi yang lebih umum akan memanggil fungsi yang disediakan pengguna bersama dengan variabel status, mulai dari status awal. Karena kita harus melewati status di antara berbagai status, kita tidak akan menggunakan for-loop, tetapi sebaliknya, gunakan rekursi,

let fold_combs n k f x =
  let rec loop i s c x =
    if i < n then
      loop (i+1) s c @@
      let c = i::c and s = s + 1 and i = i + 1 in
      if s < k then loop i s c x else f c x
    else x in
  loop 0 0 [] x

Dalam C #:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
  return k == 0 ? new[] { new T[0] } :
    elements.SelectMany((e, i) =>
      elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}

Pemakaian:

var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);

Hasil:

123
124
125
134
135
145
234
235
245
345

Solusi java pendek:

import java.util.Arrays;

public class Combination {
    public static void main(String[] args){
        String[] arr = {"A","B","C","D","E","F"};
        combinations2(arr, 3, 0, new String[3]);
    }

    static void combinations2(String[] arr, int len, int startPosition, String[] result){
        if (len == 0){
            System.out.println(Arrays.toString(result));
            return;
        }       
        for (int i = startPosition; i <= arr.length-len; i++){
            result[result.length - len] = arr[i];
            combinations2(arr, len-1, i+1, result);
        }
    }       
}

Hasilnya akan

[A, B, C]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[A, D, E]
[A, D, F]
[A, E, F]
[B, C, D]
[B, C, E]
[B, C, F]
[B, D, E]
[B, D, F]
[B, E, F]
[C, D, E]
[C, D, F]
[C, E, F]
[D, E, F]

Bolehkah saya menyajikan solusi Python rekursif saya untuk masalah ini?

def choose_iter(elements, length):
    for i in xrange(len(elements)):
        if length == 1:
            yield (elements[i],)
        else:
            for next in choose_iter(elements[i+1:len(elements)], length-1):
                yield (elements[i],) + next
def choose(l, k):
    return list(choose_iter(l, k))

Contoh penggunaan:

>>> len(list(choose_iter("abcdefgh",3)))
56

Saya suka karena kesederhanaannya.

Katakanlah susunan huruf Anda terlihat seperti ini: "ABCDEFGH". Anda memiliki tiga indeks (i, j, k) yang menunjukkan huruf mana yang akan Anda gunakan untuk kata saat ini, Anda mulai dengan:

ABCD EFGH
^ ^ ^
ijk

Pertama Anda bervariasi k, sehingga langkah selanjutnya terlihat seperti itu:

ABCD EFGH
^ ^ ^
ijk

Jika Anda mencapai akhir, Anda melanjutkan dan memvariasikan j lalu k lagi.

ABCD EFGH
^ ^ ^
ijk

ABCD EFGH
^ ^ ^
ijk

Begitu Anda mencapai G, Anda juga mulai memvariasikan i.

ABCD EFGH
  ^ ^ ^
  ijk

ABCD EFGH
  ^ ^ ^
  ijk
...

Ditulis dalam kode ini terlihat seperti itu

void print_combinations(const char *string)
{
    int i, j, k;
    int len = strlen(string);

    for (i = 0; i < len - 2; i++)
    {
        for (j = i + 1; j < len - 1; j++)
        {
            for (k = j + 1; k < len; k++)
                printf("%c%c%c\n", string[i], string[j], string[k]);
        }
    }
}

Algoritma rekursif berikut mengambil semua kombinasi elemen-k dari set yang dipesan:

• pilih elemen pertama ikombinasi Anda
• menggabungkan idengan masing-masing kombinasi k-1elemen yang dipilih secara rekursif dari set elemen yang lebih besar dari i.

Iterasi di atas untuk masing-masing idi set.

Sangat penting bagi Anda untuk memilih sisa elemen yang lebih besar daripada i, untuk menghindari pengulangan. Dengan cara ini [3,5] akan dipilih hanya sekali, karena [3] dikombinasikan dengan [5], bukan dua kali (kondisi ini menghilangkan [5] + [3]). Tanpa kondisi ini Anda mendapatkan variasi, bukan kombinasi.

Dalam C ++ rutin berikut akan menghasilkan semua kombinasi jarak panjang (pertama, k) antara rentang [pertama, terakhir):

#include <algorithm>

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

Dapat digunakan seperti ini:

#include <string>
#include <iostream>

int main()
{
    std::string s = "12345";
    std::size_t comb_size = 3;
    do
    {
        std::cout << std::string(s.begin(), s.begin() + comb_size) << std::endl;
    } while (next_combination(s.begin(), s.begin() + comb_size, s.end()));

    return 0;
}

Ini akan mencetak yang berikut ini:

123
124
125
134
135
145
234
235
245
345

Saya menemukan utas ini bermanfaat dan saya pikir saya akan menambahkan solusi Javascript yang bisa Anda masukkan ke Firebug. Tergantung pada mesin JS Anda, mungkin butuh sedikit waktu jika string awal besar.

function string_recurse(active, rest) {
    if (rest.length == 0) {
        console.log(active);
    } else {
        string_recurse(active + rest.charAt(0), rest.substring(1, rest.length));
        string_recurse(active, rest.substring(1, rest.length));
    }
}
string_recurse("", "abc");

Outputnya harus sebagai berikut:

abc
ab
ac
a
bc
b
c

static IEnumerable<string> Combinations(List<string> characters, int length)
{
    for (int i = 0; i < characters.Count; i++)
    {
        // only want 1 character, just return this one
        if (length == 1)
            yield return characters[i];

        // want more than one character, return this one plus all combinations one shorter
        // only use characters after the current one for the rest of the combinations
        else
            foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
                yield return characters[i] + next;
    }
}

Contoh singkat dengan Python:

def comb(sofar, rest, n):
    if n == 0:
        print sofar
    else:
        for i in range(len(rest)):
            comb(sofar + rest[i], rest[i+1:], n-1)

>>> comb("", "abcde", 3)
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde

Untuk penjelasan, metode rekursif dijelaskan dengan contoh berikut:

Contoh: ABCDE
Semua kombinasi 3 adalah:

• A dengan semua kombinasi 2 dari yang lain (BCDE)
• B dengan semua kombinasi 2 dari yang lainnya (CDE)
• C dengan semua kombinasi 2 dari yang lain (DE)

Algoritma rekursif sederhana di Haskell

import Data.List

combinations 0 lst = [[]]
combinations n lst = do
    (x:xs) <- tails lst
    rest   <- combinations (n-1) xs
    return $ x : rest

Kami pertama-tama mendefinisikan kasus khusus, yaitu memilih elemen nol. Ini menghasilkan hasil tunggal, yang merupakan daftar kosong (yaitu daftar yang berisi daftar kosong).

Untuk n> 0, xtelusuri setiap elemen daftar dan xssetiap elemen setelahnyax .

restmengambil n - 1elemen dari xsmenggunakan panggilan rekursif ke combinations. Hasil akhir dari fungsi adalah daftar di mana setiap elemen x : rest(yaitu daftar yang memiliki xkepala dan restekor) untuk setiap nilai berbeda dari xdan rest.

> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

Dan tentu saja, karena Haskell malas, daftar ini secara bertahap dihasilkan sesuai kebutuhan, sehingga Anda dapat mengevaluasi sebagian kombinasi besar secara eksponensial.

> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
 "abcdefgo","abcdefgp","abcdefgq"]

Dan inilah kakek COBOL, bahasa yang banyak difitnah.

Mari kita asumsikan sebuah array yang terdiri dari 34 elemen masing-masing 8 byte (murni seleksi arbitrer). Idenya adalah untuk menghitung semua kemungkinan kombinasi 4-elemen dan memuatnya ke dalam sebuah array.

Kami menggunakan 4 indeks, masing-masing satu untuk setiap posisi dalam grup 4

Array diproses seperti ini:

    idx1 = 1
    idx2 = 2
    idx3 = 3
    idx4 = 4

Kami memvariasikan idx4 dari 4 hingga akhir. Untuk setiap idx4 kami mendapatkan kombinasi unik dari kelompok empat. Ketika idx4 sampai di akhir array, kami menambah idx3 dengan 1 dan mengatur idx4 ke idx3 + 1. Kemudian kita jalankan idx4 sampai akhir lagi. Kami melanjutkan dengan cara ini, menambah masing-masing idx3, idx2, dan idx1 sampai posisi idx1 kurang dari 4 dari akhir array. Itu menyelesaikan algoritme.

1          --- pos.1
2          --- pos 2
3          --- pos 3
4          --- pos 4
5
6
7
etc.

Iterasi pertama:

1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.

Contoh COBOL:

01  DATA_ARAY.
    05  FILLER     PIC X(8)    VALUE  "VALUE_01".
    05  FILLER     PIC X(8)    VALUE  "VALUE_02".
  etc.
01  ARAY_DATA    OCCURS 34.
    05  ARAY_ITEM       PIC X(8).

01  OUTPUT_ARAY   OCCURS  50000   PIC X(32).

01   MAX_NUM   PIC 99 COMP VALUE 34.

01  INDEXXES  COMP.
    05  IDX1            PIC 99.
    05  IDX2            PIC 99.
    05  IDX3            PIC 99.
    05  IDX4            PIC 99.
    05  OUT_IDX   PIC 9(9).

01  WHERE_TO_STOP_SEARCH          PIC 99  COMP.

* Stop the search when IDX1 is on the third last array element:

COMPUTE WHERE_TO_STOP_SEARCH = MAX_VALUE - 3     

MOVE 1 TO IDX1

PERFORM UNTIL IDX1 > WHERE_TO_STOP_SEARCH
   COMPUTE IDX2 = IDX1 + 1
   PERFORM UNTIL IDX2 > MAX_NUM
      COMPUTE IDX3 = IDX2 + 1
      PERFORM UNTIL IDX3 > MAX_NUM
         COMPUTE IDX4 = IDX3 + 1
         PERFORM UNTIL IDX4 > MAX_NUM
            ADD 1 TO OUT_IDX
            STRING  ARAY_ITEM(IDX1)
                    ARAY_ITEM(IDX2)
                    ARAY_ITEM(IDX3)
                    ARAY_ITEM(IDX4)
                    INTO OUTPUT_ARAY(OUT_IDX)
            ADD 1 TO IDX4
         END-PERFORM
         ADD 1 TO IDX3
      END-PERFORM
      ADD 1 TO IDX2
   END_PERFORM
   ADD 1 TO IDX1
END-PERFORM.

Berikut ini adalah implementasi generik yang elegan di Scala, seperti dijelaskan pada 99 Masalah Scala .

object P26 {
  def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = 
    ls match {
      case Nil => Nil
      case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
    }

  def combinations[A](n: Int, ls: List[A]): List[List[A]] =
    if (n == 0) List(Nil)
    else flatMapSublists(ls) { sl =>
      combinations(n - 1, sl.tail) map {sl.head :: _}
    }
}

Jika Anda dapat menggunakan sintaks SQL - katakanlah, jika Anda menggunakan LINQ untuk mengakses bidang struktur atau array, atau langsung mengakses database yang memiliki tabel yang disebut "Alfabet" dengan hanya satu bidang char "Surat", Anda dapat beradaptasi mengikuti kode:

SELECT A.Letter, B.Letter, C.Letter
FROM Alphabet AS A, Alphabet AS B, Alphabet AS C
WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter
AND A.Letter<B.Letter AND B.Letter<C.Letter

Ini akan mengembalikan semua kombinasi dari 3 huruf, terlepas dari berapa banyak huruf yang Anda miliki dalam tabel "Alfabet" (bisa 3, 8, 10, 27, dll.).

Jika yang Anda inginkan adalah semua permutasi, bukan kombinasi (yaitu Anda ingin "ACB" dan "ABC" dihitung sebagai berbeda, daripada muncul sekali saja) hapus saja baris terakhir (DAN DAN satu) dan selesai.

Post-Edit: Setelah membaca kembali pertanyaan, saya menyadari apa yang dibutuhkan adalah algoritma umum , bukan hanya yang spesifik untuk kasus memilih 3 item. Jawaban Adam Hughes adalah jawaban yang lengkap, sayangnya saya belum bisa memberikan suaranya. Jawaban ini sederhana tetapi hanya berfungsi bila Anda menginginkan 3 item.

Versi C # lainnya dengan generasi malas dari indeks kombinasi. Versi ini mempertahankan satu larik indeks untuk menentukan pemetaan antara daftar semua nilai dan nilai untuk kombinasi saat ini, yaitu terus-menerus menggunakan ruang tambahan O (k) selama seluruh runtime. Kode menghasilkan kombinasi individual, termasuk yang pertama, di O (k) .

public static IEnumerable<T[]> Combinations<T>(this T[] values, int k)
{
    if (k < 0 || values.Length < k)
        yield break; // invalid parameters, no combinations possible

    // generate the initial combination indices
    var combIndices = new int[k];
    for (var i = 0; i < k; i++)
    {
        combIndices[i] = i;
    }

    while (true)
    {
        // return next combination
        var combination = new T[k];
        for (var i = 0; i < k; i++)
        {
            combination[i] = values[combIndices[i]];
        }
        yield return combination;

        // find first index to update
        var indexToUpdate = k - 1;
        while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= values.Length - k + indexToUpdate)
        {
            indexToUpdate--;
        }

        if (indexToUpdate < 0)
            yield break; // done

        // update combination indices
        for (var combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < k; indexToUpdate++, combIndex++)
        {
            combIndices[indexToUpdate] = combIndex;
        }
    }
}

Kode uji:

foreach (var combination in new[] {'a', 'b', 'c', 'd', 'e'}.Combinations(3))
{
    System.Console.WriteLine(String.Join(" ", combination));
}

Keluaran:

a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e

https://gist.github.com/3118596

Ada implementasi untuk JavaScript. Ini memiliki fungsi untuk mendapatkan k-kombinasi dan semua kombinasi dari array objek apa pun. Contoh:

k_combinations([1,2,3], 2)
-> [[1,2], [1,3], [2,3]]

combinations([1,2,3])
-> [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

Di sini Anda memiliki versi malas yang dievaluasi dari algoritma yang dikodekan dalam C #:

    static bool nextCombination(int[] num, int n, int k)
    {
        bool finished, changed;

        changed = finished = false;

        if (k > 0)
        {
            for (int i = k - 1; !finished && !changed; i--)
            {
                if (num[i] < (n - 1) - (k - 1) + i)
                {
                    num[i]++;
                    if (i < k - 1)
                    {
                        for (int j = i + 1; j < k; j++)
                        {
                            num[j] = num[j - 1] + 1;
                        }
                    }
                    changed = true;
                }
                finished = (i == 0);
            }
        }

        return changed;
    }

    static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
    {
        T[] elem = elements.ToArray();
        int size = elem.Length;

        if (k <= size)
        {
            int[] numbers = new int[k];
            for (int i = 0; i < k; i++)
            {
                numbers[i] = i;
            }

            do
            {
                yield return numbers.Select(n => elem[n]);
            }
            while (nextCombination(numbers, size, k));
        }
    }

Dan bagian uji:

    static void Main(string[] args)
    {
        int k = 3;
        var t = new[] { "dog", "cat", "mouse", "zebra"};

        foreach (IEnumerable<string> i in Combinations(t, k))
        {
            Console.WriteLine(string.Join(",", i));
        }
    }

Semoga ini bisa membantu Anda!

Saya memiliki algoritma permutasi yang saya gunakan untuk project euler, dengan python:

def missing(miss,src):
    "Returns the list of items in src not present in miss"
    return [i for i in src if i not in miss]


def permutation_gen(n,l):
    "Generates all the permutations of n items of the l list"
    for i in l:
        if n<=1: yield [i]
        r = [i]
        for j in permutation_gen(n-1,missing([i],l)):  yield r+j

Jika

n<len(l) 

Anda harus memiliki semua kombinasi yang Anda butuhkan tanpa pengulangan, apakah Anda membutuhkannya?

Ini adalah generator, jadi Anda menggunakannya dalam sesuatu seperti ini:

for comb in permutation_gen(3,list("ABCDEFGH")):
    print comb 

Array.prototype.combs = function(num) {

    var str = this,
        length = str.length,
        of = Math.pow(2, length) - 1,
        out, combinations = [];

    while(of) {

        out = [];

        for(var i = 0, y; i < length; i++) {

            y = (1 << i);

            if(y & of && (y !== of))
                out.push(str[i]);

        }

        if (out.length >= num) {
           combinations.push(out);
        }

        of--;
    }

    return combinations;
}

Versi clojure:

(defn comb [k l]
  (if (= 1 k) (map vector l)
      (apply concat
             (map-indexed
              #(map (fn [x] (conj x %2))
                    (comb (dec k) (drop (inc %1) l)))
              l))))

Katakanlah susunan huruf Anda terlihat seperti ini: "ABCDEFGH". Anda memiliki tiga indeks (i, j, k) yang menunjukkan huruf mana yang akan Anda gunakan untuk kata saat ini, Anda mulai dengan:

ABCD EFGH
^ ^ ^
ijk

Pertama Anda bervariasi k, sehingga langkah selanjutnya terlihat seperti itu:

ABCD EFGH
^ ^ ^
ijk

Jika Anda mencapai akhir, Anda melanjutkan dan memvariasikan j lalu k lagi.

ABCD EFGH
^ ^ ^
ijk

ABCD EFGH
^ ^ ^
ijk

Begitu Anda mencapai G, Anda juga mulai memvariasikan i.

ABCD EFGH
  ^ ^ ^
  ijk

ABCD EFGH
  ^ ^ ^
  ijk
...

function initializePointers($cnt) {
    $pointers = [];

    for($i=0; $i<$cnt; $i++) {
        $pointers[] = $i;
    }

    return $pointers;     
}

function incrementPointers(&$pointers, &$arrLength) {
    for($i=0; $i<count($pointers); $i++) {
        $currentPointerIndex = count($pointers) - $i - 1;
        $currentPointer = $pointers[$currentPointerIndex];

        if($currentPointer < $arrLength - $i - 1) {
           ++$pointers[$currentPointerIndex];

           for($j=1; ($currentPointerIndex+$j)<count($pointers); $j++) {
                $pointers[$currentPointerIndex+$j] = $pointers[$currentPointerIndex]+$j;
           }

           return true;
        }
    }

    return false;
}

function getDataByPointers(&$arr, &$pointers) {
    $data = [];

    for($i=0; $i<count($pointers); $i++) {
        $data[] = $arr[$pointers[$i]];
    }

    return $data;
}

function getCombinations($arr, $cnt)
{
    $len = count($arr);
    $result = [];
    $pointers = initializePointers($cnt);

    do {
        $result[] = getDataByPointers($arr, $pointers);
    } while(incrementPointers($pointers, count($arr)));

    return $result;
}

$result = getCombinations([0, 1, 2, 3, 4, 5], 3);
print_r($result);

Berdasarkan https://stackoverflow.com/a/127898/2628125 , tetapi lebih abstrak, untuk berbagai ukuran pointer.

Semua dikatakan dan dilakukan di sini datang kode O'caml untuk itu. Algoritma terbukti dari kode ..

let combi n lst =
    let rec comb l c =
        if( List.length c = n) then [c] else
        match l with
        [] -> []
        | (h::t) -> (combi t (h::c))@(combi t c)
    in
        combi lst []
;;

Berikut adalah metode yang memberi Anda semua kombinasi ukuran yang ditentukan dari string panjang acak. Mirip dengan solusi quinmars, tetapi berfungsi untuk beragam input dan k.

Kode dapat diubah untuk membungkus, yaitu 'dab' dari input 'abcd' wk = 3.

public void run(String data, int howMany){
    choose(data, howMany, new StringBuffer(), 0);
}


//n choose k
private void choose(String data, int k, StringBuffer result, int startIndex){
    if (result.length()==k){
        System.out.println(result.toString());
        return;
    }

    for (int i=startIndex; i<data.length(); i++){
        result.append(data.charAt(i));
        choose(data,k,result, i+1);
        result.setLength(result.length()-1);
    }
}

Output untuk "abcde":

abc abd abe acd ace ade bcd bce bde cde

kode python pendek, menghasilkan posisi indeks

def yield_combos(n,k):
    # n is set size, k is combo size

    i = 0
    a = [0]*k

    while i > -1:
        for j in range(i+1, k):
            a[j] = a[j-1]+1
        i=j
        yield a
        while a[i] == i + n - k:
            i -= 1
        a[i] += 1

Saya membuat solusi dalam SQL Server 2005 untuk ini, dan mempostingnya di situs web saya: http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm

Berikut ini adalah contoh untuk menunjukkan penggunaan:

SELECT * FROM dbo.fn_GetMChooseNCombos('ABCD', 2, '')

hasil:

Word
----
AB
AC
AD
BC
BD
CD

(6 row(s) affected)

Inilah proposisi saya di C ++

Saya mencoba untuk memaksakan pembatasan sedikit pada jenis iterator yang saya bisa jadi solusi ini mengasumsikan hanya meneruskan iterator, dan itu bisa menjadi const_iterator. Ini harus bekerja dengan wadah standar apa pun. Dalam kasus di mana argumen tidak masuk akal, ia melempar std :: invalid_argumnent

#include <vector>
#include <stdexcept>

template <typename Fci> // Fci - forward const iterator
std::vector<std::vector<Fci> >
enumerate_combinations(Fci begin, Fci end, unsigned int combination_size)
{
    if(begin == end && combination_size > 0u)
        throw std::invalid_argument("empty set and positive combination size!");
    std::vector<std::vector<Fci> > result; // empty set of combinations
    if(combination_size == 0u) return result; // there is exactly one combination of
                                              // size 0 - emty set
    std::vector<Fci> current_combination;
    current_combination.reserve(combination_size + 1u); // I reserve one aditional slot
                                                        // in my vector to store
                                                        // the end sentinel there.
                                                        // The code is cleaner thanks to that
    for(unsigned int i = 0u; i < combination_size && begin != end; ++i, ++begin)
    {
        current_combination.push_back(begin); // Construction of the first combination
    }
    // Since I assume the itarators support only incrementing, I have to iterate over
    // the set to get its size, which is expensive. Here I had to itrate anyway to  
    // produce the first cobination, so I use the loop to also check the size.
    if(current_combination.size() < combination_size)
        throw std::invalid_argument("combination size > set size!");
    result.push_back(current_combination); // Store the first combination in the results set
    current_combination.push_back(end); // Here I add mentioned earlier sentinel to
                                        // simplyfy rest of the code. If I did it 
                                        // earlier, previous statement would get ugly.
    while(true)
    {
        unsigned int i = combination_size;
        Fci tmp;                            // Thanks to the sentinel I can find first
        do                                  // iterator to change, simply by scaning
        {                                   // from right to left and looking for the
            tmp = current_combination[--i]; // first "bubble". The fact, that it's 
            ++tmp;                          // a forward iterator makes it ugly but I
        }                                   // can't help it.
        while(i > 0u && tmp == current_combination[i + 1u]);

        // Here is probably my most obfuscated expression.
        // Loop above looks for a "bubble". If there is no "bubble", that means, that
        // current_combination is the last combination, Expression in the if statement
        // below evaluates to true and the function exits returning result.
        // If the "bubble" is found however, the ststement below has a sideeffect of 
        // incrementing the first iterator to the left of the "bubble".
        if(++current_combination[i] == current_combination[i + 1u])
            return result;
        // Rest of the code sets posiotons of the rest of the iterstors
        // (if there are any), that are to the right of the incremented one,
        // to form next combination

        while(++i < combination_size)
        {
            current_combination[i] = current_combination[i - 1u];
            ++current_combination[i];
        }
        // Below is the ugly side of using the sentinel. Well it had to haave some 
        // disadvantage. Try without it.
        result.push_back(std::vector<Fci>(current_combination.begin(),
                                          current_combination.end() - 1));
    }
}

Berikut adalah kode yang baru-baru ini saya tulis di Jawa, yang menghitung dan mengembalikan semua kombinasi elemen "num" dari elemen "outOf".

// author: Sourabh Bhat ([email protected])

public class Testing
{
    public static void main(String[] args)
    {

// Test case num = 5, outOf = 8.

        int num = 5;
        int outOf = 8;
        int[][] combinations = getCombinations(num, outOf);
        for (int i = 0; i < combinations.length; i++)
        {
            for (int j = 0; j < combinations[i].length; j++)
            {
                System.out.print(combinations[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static int[][] getCombinations(int num, int outOf)
    {
        int possibilities = get_nCr(outOf, num);
        int[][] combinations = new int[possibilities][num];
        int arrayPointer = 0;

        int[] counter = new int[num];

        for (int i = 0; i < num; i++)
        {
            counter[i] = i;
        }
        breakLoop: while (true)
        {
            // Initializing part
            for (int i = 1; i < num; i++)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i] = counter[i - 1] + 1;
            }

            // Testing part
            for (int i = 0; i < num; i++)
            {
                if (counter[i] < outOf)
                {
                    continue;
                } else
                {
                    break breakLoop;
                }
            }

            // Innermost part
            combinations[arrayPointer] = counter.clone();
            arrayPointer++;

            // Incrementing part
            counter[num - 1]++;
            for (int i = num - 1; i >= 1; i--)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i - 1]++;
            }
        }

        return combinations;
    }

    private static int get_nCr(int n, int r)
    {
        if(r > n)
        {
            throw new ArithmeticException("r is greater then n");
        }
        long numerator = 1;
        long denominator = 1;
        for (int i = n; i >= r + 1; i--)
        {
            numerator *= i;
        }
        for (int i = 2; i <= n - r; i++)
        {
            denominator *= i;
        }

        return (int) (numerator / denominator);
    }
}

Solusi Javascript ringkas:

Array.prototype.combine=function combine(k){    
    var toCombine=this;
    var last;
    function combi(n,comb){             
        var combs=[];
        for ( var x=0,y=comb.length;x<y;x++){
            for ( var l=0,m=toCombine.length;l<m;l++){      
                combs.push(comb[x]+toCombine[l]);           
            }
        }
        if (n<k-1){
            n++;
            combi(n,combs);
        } else{last=combs;}
    }
    combi(1,toCombine);
    return last;
}
// Example:
// var toCombine=['a','b','c'];
// var results=toCombine.combine(4);

Algoritma:

• Hitung mulai dari 1 hingga 2 ^ n.
• Konversi setiap digit ke representasi binernya.
• Terjemahkan setiap bit 'on' ke elemen set Anda, berdasarkan posisi.

Dalam C #:

void Main()
{
    var set = new [] {"A", "B", "C", "D" }; //, "E", "F", "G", "H", "I", "J" };

    var kElement = 2;

    for(var i = 1; i < Math.Pow(2, set.Length); i++) {
        var result = Convert.ToString(i, 2).PadLeft(set.Length, '0');
        var cnt = Regex.Matches(Regex.Escape(result),  "1").Count; 
        if (cnt == kElement) {
            for(int j = 0; j < set.Length; j++)
                if ( Char.GetNumericValue(result[j]) == 1)
                    Console.Write(set[j]);
            Console.WriteLine();
        }
    }
}

Mengapa ini berhasil?

Ada bijection antara himpunan bagian dari set elemen-n dan urutan n-bit.

Itu berarti kita bisa mengetahui berapa banyak himpunan bagian dengan menghitung urutan.

misalnya, empat elemen yang ditetapkan di bawah ini dapat diwakili oleh {0,1} X {0, 1} X {0, 1} X {0, 1} (atau 2 ^ 4) urutan yang berbeda.

Jadi - yang harus kita lakukan adalah menghitung 1 hingga 2 ^ n untuk menemukan semua kombinasi. (Kami mengabaikan set kosong.) Selanjutnya, terjemahkan digit ke representasi binernya. Kemudian gantikan elemen dari set Anda untuk bit 'on'.

Jika Anda hanya menginginkan k elemen hasil, hanya cetak ketika k bit 'aktif'.

(Jika Anda ingin semua himpunan bagian alih-alih himpunan panjang k, hapus bagian cnt / kElement.)

(Sebagai buktinya, lihat Matematika courseware gratis MIT untuk Ilmu Komputer, Lehman et al, bagian 11.2.2. Https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics- untuk-komputer-sains-jatuh-2010 / bacaan / )

Saya telah menulis sebuah kelas untuk menangani fungsi umum untuk bekerja dengan koefisien binomial, yang merupakan jenis masalah yang menjadi masalah Anda. Ia melakukan tugas-tugas berikut:

1. Keluarkan semua indeks-K dalam format yang bagus untuk setiap N pilih K ke file. Indeks-K dapat diganti dengan string atau huruf yang lebih deskriptif. Metode ini membuat penyelesaian masalah jenis ini cukup sepele.

2. Mengubah indeks-K menjadi indeks entri yang tepat dalam tabel koefisien binomial yang diurutkan. Teknik ini jauh lebih cepat daripada teknik yang diterbitkan sebelumnya yang mengandalkan iterasi. Itu melakukan ini dengan menggunakan properti matematika yang melekat di Segitiga Pascal. Makalah saya berbicara tentang ini. Saya percaya saya adalah orang pertama yang menemukan dan mempublikasikan teknik ini, tetapi saya bisa saja salah.

3. Mengubah indeks dalam tabel koefisien binomial yang diurutkan ke indeks K yang sesuai.

4. Menggunakan metode Mark Dominus untuk menghitung koefisien binomial, yang jauh lebih kecil kemungkinannya untuk meluap dan bekerja dengan jumlah yang lebih besar.

5. Kelas ditulis dalam .NET C # dan menyediakan cara untuk mengelola objek yang terkait dengan masalah (jika ada) dengan menggunakan daftar generik. Konstruktor kelas ini mengambil nilai bool yang disebut InitTable bahwa ketika true akan membuat daftar generik untuk menampung objek yang akan dikelola. Jika nilai ini salah, maka tidak akan membuat tabel. Tabel tidak perlu dibuat untuk melakukan 4 metode di atas. Metode pengakses disediakan untuk mengakses tabel.

6. Ada kelas tes terkait yang menunjukkan cara menggunakan kelas dan metodenya. Telah diuji secara ekstensif dengan 2 kasus dan tidak ada bug yang dikenal.

Untuk membaca tentang kelas ini dan mengunduh kodenya, lihat Tablizing The Binomial Coeffieicent .

Seharusnya tidak sulit untuk mengkonversi kelas ini ke C ++.