1

与えられた 2 進数の可能なすべての順列を見つけるための最適なアルゴリズムを探しています。

例：

2 進数は : ........1. アルゴリズムは、00000001,00000011 などの残りの 2^7 の残りの 2 進数を返す必要があります。

ありがとう、サティシュ

4

8 に答える 8

4

与えられた例は順列ではありません!

順列は、入力の並べ替えです。

したがって、入力が 00000001 の場合、00100000 と 00000010 は順列ですが、00000011 は順列ではありません。

于 2009-11-12T09:32:33.577 に答える
4

これが小さい数 (おそらく最大 16 ビット) のみの場合は、それらすべてを反復処理し、不一致を無視します。

int fixed = 0x01; // this is the fixed part
int mask = 0x01; // these are the bits of the fixed part which matter
for (int i=0; i<256; i++) {
    if (i & mask == fixed) {
        print i;
    }
}
于 2009-11-12T09:35:40.017 に答える
2

すべての数値をループするよりもうまくいかないことをすべて見つけるには、たとえば、すべての 8 ビット数値をループしたい場合

for (int i =0; i < (1<<8) ; ++i)
{
  //do stuff with i
}

バイナリで出力する必要がある場合は、使用している言語の文字列フォーマット オプションを確認してください。

例えば

printf("%b",i); //C/C++ では標準ではありません

計算の場合、ほとんどの言語で基数は無関係である必要があります。

于 2009-11-12T09:27:51.433 に答える
1

私はあなたの質問を次のように読みました：「いくつかのビットが常に設定されている2進数が与えられた場合、残りの可能な2進数を作成してください」。

たとえば、1xx1 が与えられた場合: 1001、1011、1101、1111 が必要です。

O(N) アルゴリズムは次のとおりです。

ビットがマスク m で定義されているとします。ハッシュ h もあります。

n-1 未満の数値を生成するには、疑似コードで次のようにします。

カウンター = 0
0..n-1 の x の場合:
  x' = x | ~m
  h[x'] が設定されていない場合:
     h[x'] = カウンター
     カウンター += 1

コードのアイデアは、0 から n-1 までのすべての数値をウォークスルーし、事前定義されたビットを 1 に設定することです。次に、結果の数値を実行中の値にマッピングすることにより、結果の数値をメモします (まだメモ化されていない場合)。カウンター。

h のキーは順列になります。おまけとして、h[p] には順列 p の一意のインデックス番号が含まれますが、元の質問では必要ありませんでしたが、役立つ場合があります。

于 2010-08-24T20:24:03.163 に答える
1

なぜあなたはそれを複雑にするのですか！次のように簡単です。

// permutation of i  on a length K 
// Example  : decimal  i=10  is permuted over length k= 7 
//  [10]0001010-> [5] 0000101-> [66] 1000010 and 33, 80, 40, 20  etc.

main(){
int i=10,j,k=7; j=i;
do printf("%d \n", i= ( (i&1)<< k + i >>1); while (i!=j);
    }
于 2011-04-28T03:43:48.107 に答える
0

本当に順列を探している場合は、次のコードで十分です。

たとえば、特定のバイナリ文字列（パターン）のすべての可能な順列を見つけるには。

1000 の順列は 1000、0100、0010、0001 です。

void permutation(int no_ones, int no_zeroes, string accum){
    if(no_ones == 0){
        for(int i=0;i<no_zeroes;i++){
            accum += "0";
        }

        cout << accum << endl;
        return;
    }
    else if(no_zeroes == 0){
        for(int j=0;j<no_ones;j++){
            accum += "1";
        }

        cout << accum << endl;
        return;
    }

    permutation (no_ones - 1, no_zeroes, accum + "1");
    permutation (no_ones , no_zeroes - 1, accum + "0");
}

int main(){
    string append = "";

    //finding permutation of 11000   
    permutation(2, 6, append);  //the permutations are 

    //11000
    //10100
    //10010
    //10001
    //01100
    //01010

    cin.get(); 
}
于 2012-12-29T00:44:03.403 に答える
0

n ビットのすべての文字列の組み合わせを生成する場合は、バックトラッキングを使用して問題を解決できます。

どうぞ ：

//Generating all string of n bits assuming A[0..n-1] is array of size n
public class Backtracking {

    int[] A;

    void Binary(int n){
        if(n<1){
            for(int i : A)
            System.out.print(i);
            System.out.println();
        }else{
            A[n-1] = 0;
            Binary(n-1);
            A[n-1] = 1;
            Binary(n-1);
        }
    }
    public static void main(String[] args) {
        // n is number of bits
        int n = 8;

        Backtracking backtracking = new Backtracking();
        backtracking.A = new int[n];
        backtracking.Binary(n);
    }
}
于 2014-10-09T20:12:57.907 に答える
0

次のように、使用できる順列生成アルゴリズムは多数あります。

#include <stdio.h>

void print(const int *v, const int size)
{
  if (v != 0) {
    for (int i = 0; i < size; i++) {
      printf("%4d", v[i] );
    }
    printf("\n");
  }
} // print


void visit(int *Value, int N, int k)
{
  static level = -1;
  level = level+1; Value[k] = level;

  if (level == N)
    print(Value, N);
  else
    for (int i = 0; i < N; i++)
      if (Value[i] == 0)
        visit(Value, N, i);

  level = level-1; Value[k] = 0;
}

main()
{
  const int N = 4;
  int Value[N];
  for (int i = 0; i < N; i++) {
    Value[i] = 0;
  }
  visit(Value, N, 0);
}

ソース: http://www.bearcave.com/random_hacks/permute.html

関連する定数を必要に応じて調整してください (2 進数、7 ビットなど)。

于 2009-11-12T09:27:26.500 に答える