How to make cycle over cycles in Java?

Question

I would like to make a cycle over the following elements:

[1,2,11,12,21,22,111,112,121,122,....,222222]

or for example

[1,2,3,11,12,13,21,22,23,31,32,33,111,112,113,... 333333333]

How can I make it in Java? In my particular case I use 4 digits (1,2,3,4) and the length of the last number can be from 1 to 10.

I managed to do it in Python and PHP. In the first case I used list over lists. I started from [[1],[2],] then for every element of the list I added 1 and 2, so I got [[1,1],[1,2],[2,1],[2,2]] and so on:

nchips = sum(chips)
traj = [[]]
last = [[]]    
while len(last[0]) < nchips:
    newlast = []
    for tr in last:
        for d in [1,2,3,4]:
        newlast.append(tr + [d])
    last = newlast
    traj += last

When I did it in PHP I used number with base 3. But it was a tricky and non elegant solution.

    for ($i=-1; $i<=$n; $i+=1) {

    if ($i>-1) {
        $n5 = base_convert($i,10,5);
        $n5_str = strval($n5);
        $tr = array();
        $found = 0;
        for ($j=0; $j<strlen($n5_str); $j+=1) {
        $k = $n5_str[$j];
        if ($k==0) {
            $found = 1;
            break;
        }
        array_push($tr,$k);
        }
        if ($found==1)
        continue;
    } else {
        $tr = array();
    }
}

Can it be done easily in Java?

Answer 1

If you don't care about the generation order(I mean it will first produce 1; 11; 111, before producing 1; 2; 3) use this:

public static void gen(int level) {
    if (level > 0) {
        for (int i = 0; i < level; i++)
            System.out.print(arr[i] + " ");     
        System.out.println();
    }

    if (level == 10)
        return;

    for (int i = 1; i <= 4; i++) {
        arr[level] = i;
        gen(level + 1);
    }
}

public static void main(String[] args)  {
    gen(0);
}

But if you care about the order use this:

private static int top;
private static int[] arr = new int[10]; 

public static void gen(int level) {
    if (level == top) {

        for (int i = 0; i < level; i++)
            System.out.print(arr[i] + " ");
        System.out.println();

        return;
    }

    for (int i = 1; i <= 4; i++) {
        arr[level] = i;
        gen(level + 1);
    }
}

public static void main(String[] args)  {
    for (top = 1; top <= 10; top++)
        gen(0);
}

Answer 2

This looks an awful lot like counting with digits in a given base. (Base 2 and 3 for your examples) You can easily convert an integer to a string of a given base using Integer.toString and map the characters of that string to the symbols. Example:

Integer.toString(6, 2) -> "011"

map this string to a character array and then map that array to your symbols. In your case that would be: '0' -> 1 and '1' -> 2.

This is not the most efficient solution but it lets Integer.toString do the dirty work leaving you to do a simple array transformation.

To transform the other way around you can convert from an array to a string and then use Integer.parseInt to extract the int representation again.

If you need to perform arithmetics (I guess mainly ++ and -- for the previous and next element of the cycle), do them on the integer and convert back and forth as needed.

Disclaimer: I have not coded in java for a while so the method and class names might be off.

EDIT: You can always use big int if you need more symbols than can be accomodated in 32 and and 64-bit integers.

Response to comments:

As people has commented, this approach has problems with leading zeros. The obvious solution is to add some value N^(n+1) to the integer representation before converting to a string where N is the base and n is the number of symbols. This will have the effect of converting 1,1,2 to 1001 instead of 001 effectively allowing the zeros.

But this has the disadvantage of becoming a too complex solution to actually be the simple solution as it initially intended to be.

Answer 3

I believe your task is a combinatorial task and you should implement combinatorial algorithm to find unique combinations of given numbers (1,2,3,4) - and iterate this algorithm from 1 to desirable length.

And I can't imagine what specific features of Java you can use here. It will be some iterators.

For discussion of algorithms I advice you to read http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n

Answer 4

public class Cycle {
    static void advance(StringBuilder sb, int B) {
        int pos = sb.length();
        while (--pos != -1 && sb.charAt(pos) == '0' + B) {
            sb.setCharAt(pos, '1');
        }
        if (pos == -1) {
            sb.insert(++pos, '0');
        }
        sb.setCharAt(pos, (char) (sb.charAt(pos) + 1));
    }

    public static void main(String args[]) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < 20; i++) {
            advance(sb, 3);
            System.out.println(sb);
        }
    }
}

Advancing is done as follows:

• Go right to left (--pos)
• Rollover all Bs to 1s
• Until you find something less than B or you hit the wall (pos == -1)
• If you hit the wall, insert 0
• Increment character at pos