Python

import itertools

def kbits(n, k):
    result = []
    for bits in itertools.combinations(range(n), k):
        s = ['0'] * n
        for bit in bits:
            s[bit] = '1'
        result.append(''.join(s))
    return result

print kbits(4, 3)

Output: ['1110', '1101', '1011', '0111']

Wyjaśnienie:

Zasadniczo musimy wybrać pozycje 1-bitów. Istnieje n wybierz K sposoby wyboru K bitów spośród n bitów całkowitych. itertools to fajny moduł, który robi to za nas. itertools.kombinacje(range (n), k) wybierają bity k z [0, 1, 2 ... n-1] i wtedy to tylko kwestia zbudowania ciągu podanego przez te indeksy bitowe.

Ponieważ nie używasz Pythona, spójrz na pseudo-kod dla itertools.kombinacje tutaj:

Http://docs.python.org/library/itertools.html#itertools.combinations

Powinny być łatwe do zaimplementowania w dowolnym języku.

Zapomnij o implementacji ("be it done with strings" to oczywiście implementacja!) -- pomyśl o algorytmie , na litość boską... tak jak w, twój pierwszy TAG, człowieku!

To, czego szukasz, to wszystkie kombinacje elementów K ze zbioru N (indeksy, 0 do N-1 , zbioru bitów). Jest to oczywiście najprostsze do wyrażenia rekurencyjnie, np. pseudocode:

combinations(K, setN):
  if k > length(setN): return "no combinations possible"
  if k == 0: return "empty combination"
  # combinations including the first item:
  return ((first-item-of setN) combined combinations(K-1, all-but-first-of setN))
   union combinations(K, all-but-first-of setN)

Tzn. pierwszy element jest obecny lub nieobecny: jeśli jest obecny, masz K-1 aby przejść (od ogona aka all-but-firs), jeśli nieobecny, nadal K lewo, aby przejść.

Języki funkcyjne dopasowane do wzorców, takie jak SML lub Haskell, mogą najlepiej wyrazić ten pseudokod (proceduralne, takie jak moja wielka miłość Python, mogą faktycznie maskować problem zbyt głęboko, włączając zbyt bogatą funkcjonalność, taką jak itertools.combinations, która wykonuje całą ciężką pracę za Ciebie i dlatego ukrywa go przed tobą!).

Co najbardziej znasz, do tego celu -- Scheme, SML, Haskell, ...? Z przyjemnością. Przetłumacz powyższy pseudokod dla Ciebie. Oczywiście mogę to zrobić również w językach takich jak Python - ale ponieważ chodzi o to, abyś zrozumiał mechanikę tego zadania domowego, Nie będę używał zbyt bogatej funkcjonalności, takiej jak itertools.combinations, ale raczej rekursji (i rekursji-eliminacji, jeśli zajdzie taka potrzeba) na bardziej oczywistych prymitywach (takich jak głowa, ogon i konkatenacja). Ale daj nam znać, jaki język pseudokodowy znasz najbardziej! (Rozumiesz, że problem ty stan jest identycznie equipotent do " get all combinations of K items out or range(N)", prawda?).

Ta metoda C# zwraca enumerator, który tworzy wszystkie kombinacje. Ponieważ tworzy kombinacje, jak je wyliczyć, używa tylko przestrzeni stosu, więc nie jest ograniczona przez przestrzeń pamięci w liczbie kombinacji, które może utworzyć.

static IEnumerable<string> BinStrings(int length, int bits) {
  if (length == 1) {
    yield return bits.ToString();
  } else {
    if (length > bits) {
      foreach (string s in BinStrings(length - 1, bits)) {
        yield return "0" + s;
      }
    }
    if (bits > 0) {
      foreach (string s in BinStrings(length - 1, bits - 1)) {
        yield return "1" + s;
      }
    }
  }
}

Jest to druga wersja, która używa Splitu binarnego zamiast rozdzielania pierwszego znaku, więc używa stosu znacznie wydajniej. Jest on ograniczony tylko przestrzenią pamięci dla ciągu, który tworzy w każdej iteracji, i Przetestowałem go do długości 10000000:

static IEnumerable<string> BinStrings(int length, int bits) {
  if (length == 1) {
    yield return bits.ToString();
  } else {
    int first = length / 2;
    int last = length - first;
    int low = Math.Max(0, bits - last);
    int high = Math.Min(bits, first);
    for (int i = low; i <= high; i++) {
      foreach (string f in BinStrings(first, i)) {
        foreach (string l in BinStrings(last, bits - i)) {
          yield return f + l;
        }
      }
    }
  }
}

Jednym z problemów ze standardowymi rozwiązaniami tego problemu jest to, że cały zbiór łańcuchów jest generowany, a następnie są one iterowane, co może wyczerpać stos. Szybko staje się nieporęczny dla każdego, ale najmniejszego zestawu. Ponadto, w wielu przypadkach, tylko częściowe pobieranie próbek jest potrzebne, ale standardowe (rekurencyjne) rozwiązania na ogół chop problem na kawałki, które są mocno stronniczy w jednym kierunku(np. rozważmy wszystkie rozwiązania z zerowym bitem początkowym, a następnie wszystkie rozwiązania z jednym bitem startowym).

W wielu przypadkach byłoby bardziej pożądane, aby móc przekazać ciąg bitowy (określający wybór elementu) do funkcji i zwrócić następny ciąg bitowy w taki sposób, aby mieć minimalną zmianę (Jest to znany jako szary kod) i mieć reprezentację wszystkich elementów.

Donald Knuth opisuje całą gamę algorytmów w swojej fascynacji 3A, sekcja 7.2.1.3: generowanie wszystkich kombinacji.

Istnieje podejście do rozwiązywania iteracyjnego algorytmu szarego kodu dla wszystkich sposobów wyboru elementów k Z n na http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl z linkiem do końcowego kodu PHP podanym w komentarzu (Kliknij, aby go rozwinąć) na dole strony.

Jeden możliwy 1,5-liner:

$ python -c 'import itertools; \
             print set([ n for n in itertools.permutations("0111", 4)])'

set([('1', '1', '1', '0'), ('0', '1', '1', '1'), ..., ('1', '0', '1', '1')])

.. gdzie k jest liczbą 1 s W "0111".

Jeden algorytm, który powinien działać:

generate-strings(prefix, len, numBits) -> String:
    if (len == 0):
        print prefix
        return
    if (len == numBits):
        print prefix + (len x "1")
    generate-strings(prefix + "0", len-1, numBits)
    generate-strings(prefix + "1", len-1, numBits)

W bardziej ogólny sposób, poniższa funkcja daje wszystkie możliwe kombinacje indeksów dla problemu N wybierz K, które można następnie zastosować do ciągu znaków lub cokolwiek innego:

def generate_index_combinations(n, k):

    possible_combinations = []

    def walk(current_index, indexes_so_far=None):
        indexes_so_far = indexes_so_far or []
        if len(indexes_so_far) == k:
            indexes_so_far = tuple(indexes_so_far)
            possible_combinations.append(indexes_so_far)
            return
        if current_index == n:
            return
        walk(current_index + 1, indexes_so_far + [current_index])
        walk(current_index + 1, indexes_so_far)

    if k == 0:
        return []
    walk(0)
    return possible_combinations

Spróbowałbym rekurencji.

Istnieje n cyfr z k z nich 1s. innym sposobem, aby zobaczyć to jest sekwencja K + 1 slotów z n-k 0s rozłożone między nimi. Oznacza to, że (bieg 0s po którym następuje 1) k razy, a następnie kolejny bieg 0s. każdy z tych biegów może mieć długość zero, ale całkowita długość musi być n-k.

Reprezentuj to jako tablicę liczb całkowitych k + 1. Konwertuj na łańcuch u dołu rekurencji.

Wywołanie rekurencyjne do głębokości n-k, metody, która zwiększa jeden element tablicy przed wywołaniem rekurencyjnym, a następnie ją zmniejsza, K + 1 razy.

Na głębokości n-k wypisuje łańcuch.

int[] run = new int[k+1];

void recur(int depth) {
    if(depth == 0){
        output();
        return;
    }

    for(int i = 0; i < k + 1; ++i){
        ++run[i];
        recur(depth - 1);
        --run[i];
    }

public static void main(string[] arrrgghhs) {
    recur(n - k);
}

Dawno nie robiłem Javy, więc pewnie są jakieś błędy w tym kodzie, ale pomysł powinien zadziałać.

Czy ciągi są szybsze od tablicy ints? Wszystkie rozwiązania poprzedzające ciągi znaków prawdopodobnie skutkują kopią ciągu przy każdej iteracji.

Więc prawdopodobnie najbardziej efektywnym sposobem będzie tablica int lub char, do której się dołącza. Java ma wydajne rozwijalne kontenery, prawda? Użyj tego, jeśli jest szybszy niż string. Lub jeśli BigInteger jest wydajny, jest z pewnością kompaktowy, ponieważ każdy bit zajmuje tylko bit, a nie cały bajt lub int. Ale potem do iteracji nad bitami trzeba & maska bitowa i przesunięcie bitowe maski do następnej pozycji bitowej. Więc pewnie wolniej, chyba że Kompilatory JIT są w tym dobre.

Dodałbym komentarz do oryginalnego pytania, ale moja karma nie jest wystarczająco wysoka. Przepraszam.

Python (functional style)

Używając python ' S itertools.combinations możesz wygenerować wszystkie wybory z k Naszego z n i mapować te wybory do tablicy binarnej za pomocą reduce

from itertools import combinations
from functools import reduce # not necessary in python 2.x

def k_bits_on(k,n):
       one_at = lambda v,i:v[:i]+[1]+v[i+1:]
       return [tuple(reduce(one_at,c,[0]*n)) for c in combinations(range(n),k)]

Przykładowe użycie:

In [4]: k_bits_on(2,5)
Out[4]:
[(0, 0, 0, 1, 1),
 (0, 0, 1, 0, 1),
 (0, 0, 1, 1, 0),
 (0, 1, 0, 0, 1),
 (0, 1, 0, 1, 0),
 (0, 1, 1, 0, 0),
 (1, 0, 0, 0, 1),
 (1, 0, 0, 1, 0),
 (1, 0, 1, 0, 0),
 (1, 1, 0, 0, 0)]

Dobrze dla to pytanie (gdzie trzeba iterować nad wszystkimi zadaniami w kolejności rosnącej ich liczby bitów zestawu), które zostało oznaczone jako DUPLIKAT tego.

Możemy po prostu iterować nad wszystkimi podmaszkami dodać je do wektora i posortować według liczby bitów zestawu.

vector<int> v;
for(ll i=mask;i>0;i=(i-1)&mask)
    v.push_back(i);
auto cmp = [](const auto &a, const auto &b){
    return __builtin_popcountll(a) < __builtin_popcountll(b);
}
v.sort(v.begin(), v.end(), cmp);

Innym sposobem byłoby iterację nad wszystkimi zadaniami N razy i dodanie liczby do wektora, jeśli liczba ustawionych bitów jest równa i w iteracji it.

Obie sposoby mają złożoność O (n*2^N)