1

我有一个问题要尝试在 Java 中解决，但我无法弄清楚我需要遵循的算法。这个问题类似于位串问题（有多少个长度为 x 的位串），但增加了一些难度。无论如何，我什至不确定解决正常位串问题的算法。

所以这是我的实际问题：我有 5 个变量。比如说 QWXY Z。每个变量可以取 3 个值之一（所以就像位串可以取 1 或 0，但这可以取 0、1 或 2）。我需要生成这个“位串”的所有可能组合。

所以一个组合可能是 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实例化 a 时指定 s的数量Generator）。希望这可以帮助！

于 2012-09-08T21:07:45.787 回答
2

你需要考虑它背后的数学。当您了解如何枚举这些字符串时，事情会变得容易得多。这不仅会产生一种明显的方式来生成字符串，而且还允许您“随机访问”它们，即您还可以编写一个get(int num)将产生第numth 个元素的方法。

数学很简单，它只涉及模运算 ( ) 和除法，当你自己%弄清楚这一点时，它真的很值得。

作为一个简单的第一个准备工作，假设您有n十进制数字。

  • 给定一个数字x，你如何得到第nth 位？
  • 给定n数字，你如何得到数字x？

在你弄清楚这一点之后，试着从10数字中抽象出来。说，练习用二进制数数。然后在三进制中，这将是您的 3 位数解决方案。

于 2012-09-08T21:41:34.307 回答
1

为此，您可以使用基数 3 计数到最大值（在您的示例中为 22222）。 BigInteger 类支持使用任意基数的输出和实例化。然而，BigInteger 类不支持 zerofill，这就是我自己添加它的原因。这是得到的解决方案：

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

这应该是一个相对容易解决的问题。

本质上，您只是在计算字符串 集合Σ^5其中Σ = { 0, 1, 2 }。

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是我们想要的字符串长度，然后将这些数字转换为三进制形式。0变成00000，3^5变成100000。

于 2012-09-08T21:54:03.807 回答