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

Question

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

0111
1011
1101
1110

n과 k가 주어지면 이를 생성하는 좋은 방법이 필요하므로 문자열을 사용하여 수행하는 것을 선호합니다.

Answer 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'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) X86 CPU에 대한 GNU C 컴파일러 고유는 후행 0의 수를 반환합니다. x86에 Microsoft 컴파일러를 사용하는 경우 Intrinsic은 _BitScanForward. 둘 다 방출 a bsf지침이지만 다른 아키텍처에는 이용할 수 있습니다. 그렇지 않은 경우 앞에서 언급 한 연속 제로 비트를 계산하는 방법 중 하나를 사용하는 것이 좋습니다. 다음은 디비전 운영자로 인해 느리게 경향이있는 다른 버전입니다. 그러나 후행 0을 계산할 필요는 없습니다.

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

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

Answer 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.combinations(range(n), k)는 [0, 1, 2 ...에서 k 비트를 선택합니다.n-1] 그런 다음 해당 비트 인덱스가 주어지면 문자열을 작성하는 문제일 뿐입니다.

Python을 사용하지 않으므로 여기에서 itertools.combinations의 의사 코드를 살펴보세요.

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

어떤 언어로든 구현하기 쉬워야 합니다.

Answer 3

구현을 잊어 버린다 ( "문자열로 완료"는 분명히 구현 문제!) - 생각에 대해 생각하십시오 연산, Pete 's Sake ...에서와 마찬가지로, 당신의 첫 번째 태그, 남자!

당신이 찾고있는 것은 n 세트의 K 항목의 모든 조합 (세트 비트의 지수, 0 ~ n-1)입니다. 예를 들어, 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)

즉, 첫 번째 항목은 존재하거나 결석합니다. 참석하면, 당신은 K-1 남은 곳으로 가야합니다 (꼬리 일명 모두에서 모든 것이 틀림 없다).

SML 또는 Haskell과 같은 패턴 매칭 기능은이 의사 코드를 표현하는 것이 가장 좋을 수 있습니다 (내 큰 사랑 파이썬과 같은 절차 적 언어는 실제로 너무 풍부한 기능을 포함하여 문제를 너무 깊이 가릴 수 있습니다. itertools.combinations, 그것은 당신을 위해 모든 노력을 기울이고 당신에게서 그것을 숨 깁니다!).

이 목적을 위해 Scheme, SML, Haskell, ...? 나는 당신을 위해 위의 의사 코드를 번역하게되어 기쁩니다. 물론 파이썬과 같은 언어로도 할 수 있습니다. 그러나 요점은이 숙제 과제의 역학을 이해하게되므로 너무 풍부한 기능을 사용하지 않을 것입니다. itertools.combinations, 보다 명백한 프리미티브 (예 : 머리, 꼬리 및 연합)에서 재귀 (필요한 경우 재귀 유동성). 그러나 가장 친숙한 의사와 같은 언어를 알려주십시오! (당신은 당신이 말한 문제가 "K 항목의 모든 조합을 얻거나 범위 (n)을 얻기 위해 동일하게 등전력이 있음을 이해합니다.)

Answer 4

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

이것은 첫 번째 문자를 분할하는 대신 이진 분할을 사용하는 두 번째 버전이므로 스택을 훨씬 더 효율적으로 사용합니다. 각 반복에서 생성하는 문자열의 메모리 공간에 의해서만 제한되며, 100000000까지 테스트했습니다.

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

Answer 5

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

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

Donald Knuth는 그의 Fascicle 3A, 섹션 7.2.1.3에서 이에 대한 전체 알고리즘을 다루고 있습니다.모든 조합을 생성합니다.

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

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

행운을 빕니다!

Answer 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

Answer 8

가능한 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')])

.. 어디 k 수입니다 1s in "0111".

IterTools 모듈은 해당 방법과 동등한 요소를 설명합니다. 동등한 것을 참조하십시오 순열 방법.

Answer 9

나는 재귀를 시도 할 것이다.

1s가있는 n 자리가 있습니다. 이것을 보는 또 다른 방법은 NK 0이 분포 된 K+1 슬롯 시퀀스입니다. 즉, (0 초, 1 K 회), 다음 0 초가 이어집니다. 이 런 중 하나는 길이가 0 일 수 있지만 총 길이는 NK 여야합니다.

이것을 K+1 정수의 배열로 표시하십시오. 재귀 하단의 문자열로 변환하십시오.

재귀 적으로 호출 NK를 호출합니다. 이는 재귀 호출 전에 배열의 한 요소를 증가시킨 다음 K+1 회 감소시키는 방법입니다.

nk 깊이에서 문자열을 출력하십시오.

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를 해본 지 오래 되었으므로이 코드에는 약간의 오류가있을 수 있지만 아이디어는 작동해야합니다.

Answer 10

문자열이 int 배열보다 빠릅니까? 문자열로 선불하는 모든 솔루션은 아마도 반복마다 문자열의 사본을 초래할 수 있습니다.

따라서 아마도 가장 효율적인 방법은 당신이 추가하는 int 또는 char 배열 일 것입니다. Java는 효율적인 재배 가능한 용기를 가지고 있습니다. 문자열보다 빠르면 사용하십시오. 또는 BigInteger가 효율적이면, 각 비트는 전체 바이트 나 int가 아닌 약간의 시간 만 소요되므로 확실히 작습니다. 그러나 비트를 반복하려면 조금씩 마스크를 마스킹하고 마스크를 다음 비트 위치로 비트로 삽입합니다. 요즘 JIT 컴파일러가 잘 작동하지 않는 한 아마도 느리게 될 것입니다.

나는이 AA 의견을 원래 질문에 게시하지만 내 업장은 충분히 높지 않습니다. 죄송합니다.

Answer 11

파이썬 (기능 스타일)

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

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

또 다른 방법은 모든 서브 마스크를 반복하고 세트 비트의 수가 i ith 반복에서 i와 같으면 벡터에 숫자를 추가하는 것입니다.

두 가지 방법 모두 O (n*2^n)의 복잡성을 갖습니다.