Ответ 1

Этот метод будет генерировать все целые числа с точно N '1' битами.

От https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

Вычислить лексикографическую следующую перестановку бит

Предположим, что у нас есть шаблон из N бит, установленный в 1 в целое число, и мы хотим следующая перестановка N 1 бит в лексикографическом смысле. Для например, если N равно 3, а бит-бит 00010011, следующие шаблоны будет 00010101, 00010110, 00011001, 00011010, 00011100, 00100011, и так далее. Ниже приведен быстрый способ вычисления следующего перестановка.

unsigned int v; // current permutation of bits
unsigned int w; // next permutation of bits

unsigned int t = v | (v - 1); // t gets v least significant 0 bits set to 1
// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));

Компилятор __builtin_ctz(v) GNU C, встроенный для процессоров x86, возвращает количество конечных нулей. Если вы используете компиляторы Microsoft для x86, внутреннее значение _BitScanForward. Они оба излучают a bsfно эквиваленты могут быть доступны для других архитектур. Если нет, то рассмотрите возможность использования одного из методов подсчета последовательные нулевые биты, упомянутые ранее. Вот еще одна версия, которая имеет тенденцию быть более медленным из-за его оператора деления, но он не требуют подсчета конечных нулей.

unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

Спасибо Дарио Снейдермани (Аргентина), который предоставил это 28 ноября 2009 года.

Ответ 2

питон

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

Объяснение:

По сути, нам нужно выбрать позиции 1-бит. Существует n вариантов выбора k битов из n суммарных битов. itertools - хороший модуль, который делает это для нас. itertools.combination(range (n), k) выберет k битов из [0, 1, 2... n-1], а затем просто строит строку с учетом этих битовых индексов.

Поскольку вы не используете Python, посмотрите псевдокод для itertools.combination здесь:

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

Должно быть легко реализовано на любом языке.

Ответ 3

Забыть о реализации ( "сделайте это с помощью строк", очевидно, является проблемой реализации!) - подумайте о алгоритме, ради Пита... так же, как и в вашей первой TAG, человек!

То, что вы ищете, это все комбинации элементов K из набора из N (индексы от 0 до N-1 от установленных бит). Это, очевидно, проще всего выразить рекурсивно, например, псевдокод:

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, первый элемент либо присутствует, либо отсутствует: если он присутствует, у вас есть K-1, оставшийся до конца (от хвоста aka all-but-firs), если он отсутствует, все еще остается слева.

Функциональные языки с шаблоном сопоставления, такие как SML или Haskell, могут лучше всего выражать этот псевдокод (процедурные, такие как моя большая любовь Python, могут на самом деле замаскировать проблему слишком глубоко, включая слишком богатые функциональные возможности, такие как itertools.combinations, которые делает всю тяжелую работу для вас, и поэтому ОТКРЫВАЕТ ее от вас!).

Чем вы больше всего знакомы с этой целью - Scheme, SML, Haskell,...? Я буду рад перевести вышеуказанный псевдокод для вас. Я тоже могу это сделать на таких языках, как Python, но, поскольку вам нужно понять механику для этого домашнего задания, я не буду использовать слишком богатые функции, такие как itertools.combinations, а скорее рекурсия ( и устранение рекурсии, если необходимо) на более очевидные примитивы (такие как голова, хвост и конкатенация). Но, пожалуйста, сообщите нам, какой язык с псевдокодом вам больше всего знакомы! (Вы понимаете, что проблема, которую вы заявляете, одинаково эквипотентна, чтобы "получить все комбинации элементов K или диапазон (N)", правильно?).

Ответ 4

Этот метод С# возвращает перечислитель, который создает все комбинации. Поскольку он создает комбинации, когда вы их перечисляете, он использует только пространство стека, поэтому он не ограничен пространством памяти в количестве комбинаций, которые он может создать.

Это первая версия, с которой я столкнулся. Он ограничен пространством стека длиной около 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;
      }
    }
  }
}

Это вторая версия, которая использует двоичный бит, а не разделение первого символа, поэтому он использует стек гораздо более эффективно. Он ограничен только пространством памяти для строки, которую он создает на каждой итерации, и я проверил ее до 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;
        }
      }
    }
  }
}

Ответ 5

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

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

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

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

Ответ 6

Один алгоритм, который должен работать:

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)

Удачи!

Ответ 7

В более общем виде приведенная ниже функция даст вам все возможные комбинации индексов для N проблемы выбора K, которую вы можете применить к строке или что-то еще:

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

Ответ 8

Python (функциональный стиль)

Используя python itertools.combinations, вы можете генерировать все варианты k нашего n и сопоставлять эти варианты с двоичным массивом с 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)]

Пример использования:

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

Ответ 9

Один возможный 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 объясняет эквиваленты для своих методов; см. эквивалент для метода переадресации .

Ответ 10

Я бы попробовал рекурсию.

Есть n цифр с k из них 1s. Другой способ увидеть это - последовательность k + 1 слотов с распределенными между ними n-k 0s. То есть (пробег 0s, за которым следует 1) k раз, затем следуют другой пробег 0s. Любой из этих прогонов может иметь длину ноль, но общая длина должна быть n-k.

Представьте это как массив из k + 1 целых чисел. Преобразуйте в строку в нижней части рекурсии.

Рекурсивно вызывать глубину n-k, метод, который увеличивает один элемент массива до рекурсивного вызова, а затем уменьшает его, k + 1 раз.

На глубине n-k выведите строку.

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

Прошло некоторое время с тех пор, как я сделал Java, поэтому в этом коде есть некоторые ошибки, но идея должна работать.

Ответ 11

Являются ли строки быстрее, чем массив ints? Все решения, предлагающие строки, вероятно, приводят к копированию строки на каждой итерации.

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

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

Ответ 12

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

Мы можем просто перебрать все подмаски, добавить их в вектор и отсортировать их по количеству установленных битов.

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

Другим способом было бы выполнить итерацию по всем подмаскам N раз и добавить число к вектору, если число установленных битов равно я в i-й итерации.

Оба способа имеют сложность O (n * 2 ^ n)