1

Javaで解決しようとしている問題があり、従う必要のあるアルゴリズムを理解できません。この問題は、ビット文字列の問題（長さxのビット文字列がいくつあるか）に似ていますが、いくつかの問題があります。とにかく、通常のビット文字列の問題を解決するためのアルゴリズムすらわかりません。

これが私の実際の問題です。5つの変数があります。QWXY Zと言います。各変数は3つの値のいずれかを取ることができます（ビット文字列のように1または0を取ることができますが、これはたとえば0、1、または2を取ることができます）。この「ビット文字列」の可能なすべての組み合わせを生成する必要があります。

したがって、1つの組み合わせは00000、別の組み合わせは10002、別の組み合わせは22222などになります。この「ビット文字列」のすべての組み合わせを印刷する必要があります。

私はこの問題を解決する方法、あるいはまともなアルゴリズムを思い付く方法に本当に困惑しています。

助けてくれてありがとう！とても有難い。

4

4 に答える 4

2

これを試して：

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Generator implements Iterable<String> {

    private int len;
    public Generator(int len) {
        this.len = len;
    }

    public Iterator<String> iterator() {
        return new Itr(len);
    }

    private class Itr implements Iterator<String> {
        private int[] a;
        private boolean done;

        public Itr(int len) {
            a = new int[len];
            done = false;
        }

        @Override
        public String next() {
            if (done) throw new NoSuchElementException();
            String s = getString();
            step(a.length - 1);
            return s;
        }

        @Override
        public boolean hasNext() { return !done; }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        private void step(int index) {
            if (a[index] == 2) {
                if (index == 0) {
                    done = true;
                    return;
                }
                a[index] = 0;
                step(index - 1);
            } else
                a[index]++;
        }

        private String getString() {
            StringBuilder s = new StringBuilder();
            for (int i : a)
                s.append(i);
            return s.toString();
        }
    }

}

次に、次のようなことを行うことができます。

Generator g = new Generator(2 /* length of resulting strings */);
for (String s : g)
    System.out.println(s);

出力：

00
10
20
01
11
21
02
12
22

基本的に、ここで行っているのは、到達するまで基数3で上向きにカウントすることだけです222...222（ここで、2インスタンス化するときにsの数が指定されますGenerator）。お役に立てれば！

于 2012-09-08T21:07:45.787 に答える
2

その背後にある数学を考慮する必要があります。これらの文字列を列挙する方法を理解すると、作業が非常に簡単になります。これにより、文字列を生成するだけでなく、文字列に「ランダムアクセス」するための明白な方法が得られます。つまり、 th要素get(int num)を生成するメソッドを作成することもできます。num

計算は非常に単純で、モジュロ演算（）と除算のみが含まれます。これを自分%で理解すると、実際に効果があります。

n簡単な最初の準備として、 10進数があると仮定します。

  • 数字が与えられた場合x、どのようにしてn3桁目を取得しますか？
  • 与えられnた数字、どのように数字を取得しますxか？

10これを理解した後、数字を持つことから抽象化してみてください。たとえば、2進数で数える練習をします。次に、3進数で、3桁のソリューションになります。

于 2012-09-08T21:41:34.307 に答える
1

これを実現するには、基数3を使用して最大値（この例では22222）までカウントアップすることができます。BigIntegerクラスは、任意の基数での出力とインスタンス化をサポートします。ただし、BigIntegerクラスはゼロフィルをサポートしていないため、これを自分で追加しました。結果のソリューションは次のとおりです。

public static void main( String[] args ) {
    System.out.println( new BitStrings().generateBitStrings( new BigInteger( "2222", 3 ) ) );
}

public List<String> generateBitStrings( BigInteger maxValue ) {
    final String format = "%0" + maxValue.toString( 3 ).length() + "d";
    BigInteger current = BigInteger.ZERO;
    final List<String> result = new ArrayList<String>( maxValue.intValue() );
    do {
        result.add( String.format( format, Long.valueOf( current.toString( 3 ) ) ) );
        current = current.add( BigInteger.ONE );
    } while(current.compareTo( maxValue ) <= 0);
    return result;
}

出力：

[0000, 0001, 0002, 0010, 0011, 0012, 0020, 0021, 0022, 0100, 0101, 0102, 0110, 0111, 0112, 0120, 0121, 0122, 0200, 0201, 0202, 0210, 0211, 0212, 0220, 0221, 0222, 1000, 1001, 1002, 1010, 1011, 1012, 1020, 1021, 1022, 1100, 1101, 1102, 1110, 1111, 1112, 1120, 1121, 1122, 1200, 1201, 1202, 1210, 1211, 1212, 1220, 1221, 1222, 2000, 2001, 2002, 2010, 2011, 2012, 2020, 2021, 2022, 2100, 2101, 2102, 2110, 2111, 2112, 2120, 2121, 2122, 2200, 2201, 2202, 2210, 2211, 2212, 2220, 2221, 2222]

これがあなたの質問に答えることを願っています。

于 2012-09-08T21:05:27.093 に答える
1

これは比較的簡単に解決できる問題です。

基本的に、 Σ= {0、1、2}である文字列 Σ^5のセットを計算しているだけです。

static Iterable<String> strings(final int radix, final int digits) {
  return new Iterable<String>() {

    public Iterator<String> iterator() {
      return new Iterator<String>() {

        private final int hi = (int) Math.pow(radix, digits);
        private int cursor;

        public boolean hasNext() {
          return cursor < hi;
        }

        public String next() {
          int v = cursor++;
          int n = digits;
          final char[] buf = new char[n];
          while (n > 0) {
            buf[--n] = (char) (v % radix + '0');
            v /= radix;
          }
          return new String(buf);
        }

        public void remove() {
          throw new UnsupportedOperationException();
        }
      };
    }
  };
}

...次のように使用できます。

for (final String val : strings(3, 5)) {
  System.out.println(val);
}

基本的に、[0、3 ^ 5）の間隔で数値を生成します。ここで、3は基数、5は目的の文字列の長さであり、数値を3部形式に変換します。0は00000になり、3^5は100000になります。

于 2012-09-08T21:54:03.807 に答える