Генерируйте все двоичные строки длины n с k набором битов

Строки быстрее, чем массив целых чисел? Все решения, добавляемые к строкам, вероятно, приведут к созданию копии строки на каждой итерации.

Так что, вероятно, наиболее эффективным способом будет добавление массива int или char. У Java есть эффективные растущие контейнеры, верно? Используйте это, если оно быстрее, чем строка. Или, если BigInteger эффективен, он определенно компактен, поскольку каждый бит занимает только бит, а не целый байт или int. Но затем, чтобы перебрать биты, вам нужно немного замаскировать и сдвинуть маску на следующую битовую позицию. Так что, вероятно, медленнее, если только JIT-компиляторы не умеют это делать в наши дни.

Я бы опубликовал этот комментарий к исходному вопросу, но моя карма недостаточно высока. Извините.

I would try recursion.

There are n digits with k of them 1s. Another way to view this is sequence of k+1 slots with n-k 0s distributed among them. That is, (a run of 0s followed by a 1) k times, then followed by another run of 0s. Any of these runs can be of length zero, but the total length needs to be n-k.

Represent this as an array of k+1 integers. Convert to a string at the bottom of the recursion.

Recursively call to depth n-k, a method that increments one element of the array before a recursive call and then decrements it, k+1 times.

At the depth of n-k, output the string.

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);
}

It's been a while since I have done Java, so there are probably some errors in this code, but the idea should work.

Один из возможных 1,5-строчных:

$ 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')])

.. где k - это количество 1 сек в «0111» .

Модуль itertools объясняет эквиваленты своих методов; см. эквивалент метода перестановки .

This C# method returns an enumerator that creates all combinations. As it creates the combinations as you enumerate them it only uses stack space, so it's not limited by memory space in the number of combinations that it can create.

This is the first version that I came up with. It's limited by the stack space to a length of about 2700:

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;
      }
    }
  }
}

This is the second version, that uses a binary split rather than splitting off the first character, so it uses the stack much more efficiently. It's only limited by the memory space for the string that it creates in each iteration, and I have tested it up to a length of 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;
        }
      }
    }
  }
}

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']

Explanation:

Essentially we need to choose the positions of the 1-bits. There are n choose k ways of choosing k bits among n total bits. itertools is a nice module that does this for us. itertools.combinations(range(n), k) will choose k bits from [0, 1, 2 ... n-1] and then it's just a matter of building the string given those bit indexes.

Since you aren't using Python, look at the pseudo-code for itertools.combinations here:

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

Should be easy to implement in any language.

One algorithm that should work:

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)

Good luck!

Forget about implementation ("be it done with strings" is obviously an implementation issue!) -- think about the algorithm, for Pete's sake... just as in, your very first TAG, man!

What you're looking for is all combinations of K items out of a set of N (the indices, 0 to N-1 , of the set bits). That's obviously simplest to express recursively, e.g., 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-1, all-but-first-of setN)

i.e., the first item is either present or absent: if present, you have K-1 left to go (from the tail aka all-but-firs), if absent, still K left to go.

Pattern-matching functional languages like SML or Haskell may be best to express this pseudocode (procedural ones, like my big love Python, may actually mask the problem too deeply by including too-rich functionality, such as itertools.combinations, which does all the hard work for you and therefore HIDES it from you!).

What are you most familiar with, for this purpose -- Scheme, SML, Haskell, ...? I'll be happy to translate the above pseudocode for you. I can do it in languages such as Python too, of course -- but since the point is getting you to understand the mechanics for this homework assignment, I won't use too-rich functionality such as itertools.combinations, but rather recursion (and recursion-elimination, if needed) on more obvious primitives (such as head, tail, and concatenation). But please DO let us know what pseudocode-like language you're most familiar with! (You DO understand that the problem you state is identically equipotent to "get all combinations of K items out or range(N)", right?).

Одна из проблем со многими стандартными решениями этой проблемы заключается в том, что создается весь набор строк, а затем они проходят итерацию, что может исчерпать стек. Он быстро становится громоздким для любых наборов, кроме самых маленьких. Кроме того, во многих случаях требуется только частичная выборка, но стандартные (рекурсивные) решения обычно разбивают проблему на части, которые сильно смещены в одном направлении (например, рассматривают все решения с нулевым начальным битом, а затем все решения с одним стартовым битом).

Во многих случаях было бы более желательно иметь возможность передать битовую строку (определяющую выбор элемента) в функцию и заставить ее возвращать следующую битовую строку таким образом, чтобы иметь минимальное изменение (это известно как код Грея) и иметь представление всех элементов.

Дональд Кнут описывает целый ряд алгоритмов для этого в своей «Части 3A», раздел 7.2.1.3: Создание всех комбинаций.

Существует подход для решения итеративного алгоритма кода Грея для всех способов выбора k элементов из n на http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl {{1 }} со ссылкой на окончательный PHP-код, указанный в комментарии (щелкните, чтобы развернуть) внизу страницы.