2

最近、1、0、? のいずれかを含む単一の文字列を取る関数を考案するように依頼されました (例: "10?10?1"、"00???11"、"???? " など) を入力として受け取り、入力文字列のすべての一意のゼロ順列を含む文字列のリストを返します。

「10?1?」を入力すると、答えは「10010」、「10110」、「10011」、「10111」を含むリストになります。

これを行う関数を考案することができましたが、それは本質的に力ずくであり、複雑さが O(2^n) であるよりクリーンな関数に興味があります。アルゴリズムおよび/または実装を提供していただければ幸いです。ありがとうございます!

4

7 に答える 7

2

「ブルートフォース」の実装よりもはるかに優れているとは思いません。N 個の疑問符を含む提供された文字列には、2^N 個の一意の順列があります。本当に、あなたができることは、好きな順序ですべての異なる弦を試すことだけです. アルゴリズムに関して：

  • 文字列内の疑問符があるすべての場所へのポインターを取得し、配列に格納します。
  • 疑問符の数よりも長いビットの符号なし整数変数を取得します (安全のために long long を使用してください)。0 に設定します。
  • 変数のビットは、疑問符のすべての可能な組み合わせを表します。したがって、ビット演算を使用して疑問符を 1 と 0 に置き換え、そのたびに変数を 1 ずつ増やします。
  • 2^N 回繰り返します。
于 2013-11-01T03:29:26.270 に答える
2

各ノードがビットであるツリーと考えることができます。各クエスチョン マークは、0 と 1 の 2 つのノードを生成します。クエスチョン マークでないものはすべて、同じ値を持つ単なるノードです。たとえば、 の入力の10?1?場合、ツリーは次のように展開されます。

ここに画像の説明を入力

C の実装は次のとおりです。

void generate_str(char *str, int pos) {
    if (str[pos] == '\0') {
        printf("%s\n", str);
        return;
    }
    if (str[pos] == '?') {
        str[pos] = '0';
        generate_str(str, pos+1);
        str[pos] = '1';
        generate_str(str, pos+1);
        str[pos] = '?'; /* We can get back to this branch because of an earlier '?' */
    }
    else {
        generate_str(str, pos+1);
    }
}

位置を「?」に戻す必要があることに注意してください。別のブランチから来た可能性があるため、そのブランチを探索した後、後で同じ位置に再び疑問符があることを認識する必要があります。

この関数は次のように呼び出すことができます。

int main(void) {
    char test[] = "10?1?";
    generate_str(test, 0);
    return 0;
}

O(2^n)少なくとも出力を印刷する必要があるため、より良いことはできません。

于 2013-11-01T09:37:16.533 に答える
1

これには再帰的な解決策があります

input_str = "10??01"

# 100001
# 100101
# 101001
# 101101

def solution(res, a, n):
  if n == 1 and a[0] != "?":
    print(res+a[0])
    return

  elif n == 1 and a[0] == "?":
    print(res+"0")
    print(res+"1")
    return


  if a[0] != "?":
    solution(res+a[0], a[1: ], len(a[1: ]))

  elif a[0] == "?":
    solution(res+"0", a[1: ], len(a[1: ]))
    solution(res+"1", a[1: ], len(a[1: ]))


solution("", input_str, len(input_str))
于 2017-11-10T19:39:09.113 に答える
0

Java で書かれていますが、c++ に簡単に変換できます。

基本は、疑問符?を単一の値に分離することです。次に、組み合わせのリストに( 0all ではなく) 1 つの値を入れます。?次に、オーブンと組み合わせのリストを反復し、そのたびbitwise orに、分離された疑問符を使用して保持する値の数を乗算します?。

乗算を d 回実行しています。ここで、d は疑問符の数です。したがって、おおよそ 2^d 時間実行しているため、O(2^d) になります。n が入力サイズの場合、O(2^n) より小さい。

スペースの複雑度は、返される配列 - O(n * 2^d) です。2^d 文字列。入力のサイズを持つ各文字列 - n。

* 入力が 64 ビットより大きい場合、マージの計算を省略しました。

public class BinaryCombinationsForQuestionMark {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(getAllCombinations("1??")));
    }

    // TODO: If larger than 64 bit, separate to 64 and merge to original sizes
    public static int[] getAllCombinations(String input) {
        // TODO: Validate input
        // Doing up to 64 bits
        int numWithZerosAsQuestions = convertToNumWithQuestionsAsZeros(input);
        int[] separated = separateToOnesAsQuestions(input);

        List<Integer> combinations = new ArrayList<>();
        combinations.add(numWithZerosAsQuestions);
        for (int separate : separated) {
            // Prevents ConcurrentModificationException
            int size = combinations.size();
            for (int i = 0; i < size; i++) {
                int combination = combinations.get(i);
                combinations.add(combination | separate);
            }
        }
        return combinations.stream().mapToInt(i -> i).toArray();
    }

    private static int[] separateToOnesAsQuestions(String input) {
        ArrayList<Integer> separated = new ArrayList<>();
        for (int i = input.length() - 1; i >= 0; --i) {
            char c = input.charAt(i);
            if (c == '?') {
                separated.add(1 << input.length() - 1 - i);
            }
        }
        return separated.stream().mapToInt(i -> i).toArray();
    }

    private static int convertToNumWithQuestionsAsZeros(String input) {
        int num = 0;
        for (int i = 0; i < input.length(); ++i) {
            num <<= 1;
            char c = input.charAt(i);
            if (c == '1') num |= 1;
        }
        return num;
    }
}

乾杯。

于 2017-11-01T21:21:32.230 に答える