How to dynamically decide how many loops I want?

Question

Here is the subject:

I have a LinkedList list, if the list has 3 elements, I'd like to list an entire truth table for it, for instance:

a b c   <---   the three elements in list
0 0 0
0 0 1
0 1 0
1 0 0
1 1 1
1 1 0
1 0 1
0 1 1

and if the list has 4 or more elements, I would like to generate a more large table.

But I got stuck here:

I know writing loops like this can generate the entire table:

       for (int a = 0; a < 2; a++){
            for (int b = 0; b < 2; b++) {
                for (int c = 0; c < 2; c++) {
                    for (int d = 0; d < 2; d++) {
                        System.out.println(a + " " + b + " " + c + " " + d);
                    }
                }
            }
        }

but I can't change the number of loops based on the list size, and I think writing special cases for this is unacceptable, so is there an alternative way to do this??

Sounds like recursion might be useful. – Sep 13 '12 at 10:07 — , Sep 13 '12 at 10:07
had read some before, why asking?@ZagorulkinDmitry – shengy Sep 13 '12 at 14:20 — shengy, Sep 13 '12 at 14:20

Prasanth · Accepted Answer · 2012-09-13T10:25:27.567

12

simple solution if you just want a truth table:

code:

int len = 3;
int num = (int)Math.pow(2, len);
for(int i=0; i<num; i++){
    // http://stackoverflow.com/a/4421438/1273830
    System.out.println(String.format("%"+len+"s", Integer.toBinaryString(i)).replace(' ', '0'));
}

Basic digital logic: truth tables are binary number sequences.

edited Sep 13 '12 at 10:25

answered Sep 13 '12 at 10:11

Prasanth

5,230
2
29
61

Thanks for the basic logic tip! – shengy Sep 14 '12 at 01:27

score 1 · Answer 2 · answered Sep 13 '12 at 10:08

The number of loops needs to match the number of elements. There are two ways to solve this.

Use recursion so that there is one loop and the method calls itself for the next level of looping.
Use a single loop which repeats 2^n times and extracts out the components values.

score 0 · Answer 3 · answered Sep 13 '12 at 10:17

0

I won't write it in Java for you, but here is a pseudocode to give you an idea how to solve the problem recursively:

l = ['a','b','c']

def f(l, result):
    if len(l) == 0:
        print result
        return
    first = l[0]
    rest = l[1:]
    f(rest, result + [(first,0)])
    f(rest, result + [(first,1)])

f (l, [])

This should print something like:

[('a', 0), ('b', 0), ('c', 0)]
[('a', 0), ('b', 0), ('c', 1)]
[('a', 0), ('b', 1), ('c', 0)]
[('a', 0), ('b', 1), ('c', 1)]
[('a', 1), ('b', 0), ('c', 0)]
[('a', 1), ('b', 0), ('c', 1)]
[('a', 1), ('b', 1), ('c', 0)]
[('a', 1), ('b', 1), ('c', 1)]

answered Sep 13 '12 at 10:17

piokuc

25,594
11
72
102

So you post an _untested_ non-java solution. Why do you post this in the first place? You should post at least pseudocode which is more java like. (Slices don't exitst in java) – Marcel Jaeschke Sep 13 '12 at 16:03
Well, shengy seemed to struggle to find an algorithm to solve the exercise, so I presented an algorithm, leaving Java implementation to him, as I thought it would be more beneficial for him education wise. – piokuc Sep 13 '12 at 16:10
You say "this should print". Thats like "I'm not sure". How do you test pseudocode? Anyway, I don't want debating here. :-) – Marcel Jaeschke Sep 14 '12 at 17:17

How to dynamically decide how many loops I want?

3 Answers3