k 비트가 설정된 길이 n의 모든 이진 문자열 생성

k 비트가 설정된 길이 n의 모든 이진 문자열 생성

---

k 비트 세트를 포함하는 길이 n의 모든 이진 문자열을 찾는 가장 좋은 알고리즘은 무엇입니까? 예를 들어 n = 4이고 k = 3이면 다음이 있습니다.

0111
1011
1101
1110

n과 k가 주어지면이를 생성하는 좋은 방법이 필요하므로 문자열로 수행하는 것이 좋습니다.

---

이 방법은 정확히 N '1'비트를 가진 모든 정수를 생성합니다.

에서 https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

사전 식으로 다음 비트 순열 계산

정수에서 1로 설정된 N 비트 패턴이 있고 사전 식적 의미에서 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's 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)86 CPU에 대한 GNU C 컴파일러 내장 함수는 후행 0의 수를 반환합니다. x86 용 Microsoft 컴파일러를 사용하는 경우 내장 함수는 _BitScanForward. 둘 다 bsf명령어를 내 보냅니다. 하지만 다른 아키텍처에서도 동일한 기능을 사용할 수 있습니다. 그렇지 않은 경우 앞에서 언급 한 연속 0 비트를 계산하는 방법 중 하나를 사용하는 것이 좋습니다. 나누기 연산자로 인해 더 느린 경향이있는 또 다른 버전이 있지만 후행 0을 세지 않아도됩니다.

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

2009 년 11 월 28 일에이를 제공 한 아르헨티나의 Dario Sneidermanis에게 감사드립니다.

---

파이썬

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 개의 비트를 선택하는 k 개의 선택 방법이 있습니다. itertools는이 작업을 수행하는 멋진 모듈입니다. itertools.combinations (range (n), k)는 [0, 1, 2 ... n-1]에서 k 비트를 선택하고 해당 비트 인덱스가 주어지면 문자열을 만드는 문제입니다.

Python을 사용하지 않으므로 여기에서 itertools.combinations에 대한 의사 코드를 살펴보십시오.

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

어떤 언어로도 쉽게 구현할 수 있어야합니다.

---

구현은 잊어 버리세요 ( "be it done with strings"는 분명히 구현 문제입니다!)- 알고리즘 에 대해 생각해보세요. Pete를 위해 ... 첫 번째 TAG와 마찬가지로 요!

당신이 찾고있는 것은 N 세트 (세트 비트의 인덱스, 0 ​​~ N-1)에서 K 항목의 모든 조합입니다. 재귀 적으로 표현하는 것이 가장 간단합니다. 예 : 의사 코드 :

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)

즉, 첫 번째 항목이 존재하거나 부재 중입니다. 존재하는 경우 K-1이 남아 있습니다 (꼬리에서 모두 제외). 없으면 K-1이 남아 있습니다.

패턴 일치 SML 또는 하스켈 같은 함수형 언어는 내 큰 사랑 파이썬 등이 의사 (절차 사람을 표현하는 것이 가장 좋습니다 실제로 같은 너무 풍부한 기능을 포함하여 너무 깊이 문제를 마스크 수 itertools.combinations를 위해 모든 노력을한다, 따라서 당신에게서 그것을 숨 깁니다!).

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?).

---

이 C # 메서드는 모든 조합을 만드는 열거자를 반환합니다. 열거 할 때 조합을 생성하므로 스택 공간 만 사용하므로 생성 할 수있는 조합 수의 메모리 공간에 의해 제한되지 않습니다.

이것이 제가 생각 해낸 첫 번째 버전입니다. 스택 공간에 따라 길이가 약 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;
        }
      }
    }
  }
}

---

이 문제에 대한 많은 표준 솔루션의 한 가지 문제는 전체 문자열 집합이 생성 된 다음 반복되어 스택이 소진 될 수 있다는 것입니다. 가장 작은 세트를 제외하고는 빠르게 다루기 어려워집니다. 또한 대부분의 경우 부분 샘플링 만 필요하지만 표준 (재귀) 솔루션은 일반적으로 문제를 한 방향으로 크게 편향된 조각으로 나눕니다 (예 : 시작 비트가 0 인 모든 솔루션을 고려한 다음 모두 고려). 하나의 시작 비트가있는 솔루션).

대부분의 경우, 비트 문자열 (요소 선택 지정)을 함수에 전달하고 최소한의 변경을 갖는 방식으로 다음 비트 문자열을 반환하도록하는 것이 더 바람직 할 것입니다 (이것은 회색이라고합니다. 코드) 및 모든 요소의 표현을 갖습니다.

Donald Knuth는 그의 Fascicle 3A 섹션 7.2.1.3 : 모든 조합 생성에서이를위한 전체 알고리즘 호스트를 다룹니다.

에서 n은 K 요소를 선택하는 모든 방법에 대한 반복적 인 그레이 코드 알고리즘을 태클에 대한 접근 방식이 http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl 주석에 나열된 최종 PHP 코드에 대한 링크는 ( 확장하려면 클릭) 페이지 하단에 있습니다.

---

작동해야하는 하나의 알고리즘 :

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)

행운을 빕니다!

---

좀 더 일반적인 방법으로, 아래 함수는 N choose 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

---

가능한 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".

The itertools module explains equivalents for its methods; see the equivalent for the permutation method.

---

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.

---

Are strings faster than an array of ints? All the solutions prepending to strings probably result in a copy of the string at each iteration.

So probably the most efficient way would be an array of int or char that you append to. Java has efficient growable containers, right? Use that, if it's faster than string. Or if BigInteger is efficient, it's certainly compact, since each bit only takes a bit, not a whole byte or int. But then to iterate over the bits you need to & mask a bit, and bitshift the mask to the next bit position. So probably slower, unless JIT compilers are good at that these days.

I would post this a a comment on the original question, but my karma isn't high enough. Sorry.

---

Python (functional style)

Using python's itertools.combinations you can generate all choices of k our of n and map those choices to a binary array with 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)]

Example usage:

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

---

Well for this question (where you need to iterate over all the submasks in increasing order of their number of set bits), which has been marked as a duplicate of this.

We can simply iterate over all the submasks add them to a vector and sort it according to the number of set bits.

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

Another way would be to iterate over all the submasks N times and add a number to the vector if the number of set bits is equal to i in the ith iteration.

Both ways have complexity of O(n*2^n)

ReferenceURL : https://stackoverflow.com/questions/1851134/generate-all-binary-strings-of-length-n-with-k-bits-set