Java Algoirthm变量组合数（类似于位字符串算法） [英] Java Algoirthm number of Combinations of variables (Similar to Bit String Algoirthm)

问题描述

我有一个用Java试图解决的问题，我无法弄清楚我需要遵循的算法。这个问题类似于位串问题（长度为x的位串有多少个），但是增加了一些难度。我什至都不确定解决普通位字符串问题的算法。

I have a problem I'm trying to solve in Java and I cannot figure out the algorithm that I'm going to need to follow. This problem is similar to the Bit String problem (how many bit strings are there of length x), but with some added difficulty. I'm not even sure the algorithm for solving the normal bit string problem anyway.

所以这是我的实际问题：
我有5个变量。说Q W X YZ。每个变量可以采用3个值之一（因此，像位字符串可以采用1或0，但是可以采用0、1或2）。我需要生成此位字符串的所有可能组合。

So here's my actual problem: I have 5 variables. Say Q W X Y Z. Each variable can take one of 3 values (so like bit string can take 1 or 0, but this can take say 0, 1, or 2). I need to generate all possible combinations of this "bit string".

因此，一个组合可能是00000，另一个可能是10002，另一个可能是22222，等等。我需要打印出这个位字符串的所有组合

So one combination may be 00000 another may be 10002, another could be 22222, etc. I need to print out all combinations of this "bit string"

我真的很困惑如何解决这个问题，甚至想出了一个不错的算法。

I'm really stumped on how to solve this problem or even come up with a decent algorithm.

感谢您的帮助！

推荐答案

要实现这一点，您可以使用基数来算出最大值（示例中为22222）之3。BigInteger类支持使用任意基数的输出和实例化。但是，BigInteger类不支持Zerofill，这就是我自己添加此类的原因。这是产生的解决方案：

To achieve this, you could just count up to your maximum value (22222 in your example) using a radix of 3. The BigInteger class supports output and instantiation with an arbitrary radix. The BigInteger class, however, does not support zerofill which is why I added this myself. Here is the resulting solution:

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]

希望这能回答您的问题。

Hope this answers your question.

这篇关于Java Algoirthm变量组合数（类似于位字符串算法）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！