Geek asks and answers

Java Algoirthm the number of combinations of variables (similar to the String Algoirthm bit)

I have a problem that I am trying to solve in Java, and I cannot understand the algorithm that I will need to execute. This problem is similar to the problem with a bit string (how many bits of strings has length x), but with some additional difficulties. I'm not even sure what the algorithm is to solve a common bit string problem anyway.

So here is my real problem: I have 5 variables. Let's say QWXY Z. Each variable can take one of 3 values ​​(so a bit bit can take 1 or 0, but it can take values ​​0, 1 or 2). I need to generate all possible combinations of this "bit string".

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

I am really fixated on how to solve this problem or even came up with a decent algorithm.

Thanks for the help! Very much appreciated.

+1
source share
4 answers

To achieve this, you can simply count to the maximum value (22222 in your example) using a radius of 3. The BigInteger class supports outputting and instantiating with an arbitrary base. However, the BigInteger class does not support zerofill, so 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;
}

Conclusion:

[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.

+1
source

Try the following:

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

, , , base-3, 222...222 ( 2 Generator). , !

+2

. , , . , " " , .. get(int num), num th.

, (%) , , .

, , n .

  • x, n th?
  • n, x?

, , 10. , . , 3 .

+2

.

, Σ ^ 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);
}

Basically, we generate numbers in the interval [0, 3 ^ 5), where 3 is our radius and 5 is the desired length of the string, and then convert the numbers to ternary . 0 becomes 00000, 3 ^ 5 becomes 100000.

+1
source

More articles:


All Articles