0

I have 20 different variable-length arrays, each holding a unique value, and I need to calculate every possible combination of these:

#define LENGTH_COUNT 6
#define WIDTH_COUNT 4
etc, for all 20 arrays:

int length[LENGTH_COUNT];
int width[WIDTH_COUNT];
int height[HEIGHT_COUNT];
int weight[WEIGHT_COUNT];
int growth[GROWTH_COUNT];
int decay[DECAY_COUNT];
int sound[SOUND_COUNT];
int texture[TEXTURE_COUNT];
int moisture[MOISTURE_COUNT];
int volume[VOLUME_COUNT];
int speed[SPEED_COUNT];
int color[COLOR_COUNT];
int purpose[PURPOSE_COUNT];
int delay[DELAY_COUNT];
int vibrancy[VIBRANCY_COUNT];
int brix[BRIX_COUNT];
int ripeness[RIPENESS_COUNT];
int mold[MOLD_COUNT];
int temp[TEMP_COUNT];
int language[LANGUAGE_COUNT];


void iterate(void)
{
    for (int i = 0; i < LENGTH_COUNT; ++i)
          for (int j = 0; j < WIDTH_COUNT; ++j)
                for (int k = 0; k < HEIGHT_COUNT; ++k)
                // etc for all 20 arrays
                    int value = doSomething(length[i], width[j], height[k].....);
}

There must be a less brain-dead way to do this. One idea I had is:

#define ARRAY_COUNT  20
#define MAX_LENGTH 12   // the longest array length is 12
int arrays[ARRAY_COUNT][MAX_LENGTH];

But if I were to do this, I don't know how to do the equivalent to what I am doing in the iterate function. Any ideas?

Improve this question
9
  • You are going to need to keep track of the size of each 'sub-array'. To make it easier, create a struct which has the maximum index of the sub-array, as well as a pointer to it. Commented Apr 5, 2012 at 1:26
  • 1
    So you need to calculate every combination of, upto 12 values (lets call it 10 for simplicity) from all 20 arrays? That is about 10^20 combinations of values? Imagine just counting from 1 to 10^20. Even if you could produce 1 value every nanosecond (10^-9 seconds) that's over 3,000 years. Are there some simplifying assumptions? What is the bigger problem 'cos I don't think this approach is the way to go. Commented Apr 5, 2012 at 1:35
  • To reduce the complexity, I omitted the parallelizing done here. Even parallelized, it would take a few years, but I am going to run it for a couple of days, and I will be able to toss out all the variables that don't have an impact on the results. So this will greatly reduce the runtime, to a few hours (acceptable). The objective: run thru all these possible combos, looking for a best fit to a certain other bit of info. Commented Apr 5, 2012 at 1:54
  • You would have to parallelize across 1000 machines to get this down to a few years. So are you saying there are no criteria (objective function) that could be used to reduce the search space dramatically? Is this an assignment? I ask because I used to set exercises like this where the insight needed was to test the usefulness of each type of value within the 'search space'. A trivial example was a word game called Bogle, which had most permutations of 16 letters. If all permutations were generated, it took years, but by constraining the search it took seconds on a 1988 IBM PC. Commented Apr 5, 2012 at 2:03
  • I see your point. The reason I wanted to do all the permutations is because while I have a hunch about which variables will be worthwhile, I would rather determine this empirically. Maybe I could constrain things by reducing all of the arrays to a length of 3, which should help me toss out all of the useless values, and get down to a reasonable number. (btw, this is an assignment...I'm in my 40's and self-employed, and my wife has assigned me the task of putting some bread on the table...) Commented Apr 5, 2012 at 2:41

2 Answers 2

Reset to default
1

You could create (untested/uncompiled):

int *arrays[] = { first_arr, second_arr, ... }; // array of arrays
int maxes[] = { FIRST_ARR_MAX, SECOND_ARR_MAX, ... }; // array of array lengths
int counter[NUM_ARRAYS] = {0}; // initialize a counter to 0 for each of the arrays.

int state = 0;

while (true) {
    doSomething(first_arr[counter[0]], second_arr[counter[1]], ... );

    // Update the counter.
    int i;
    for (i = NUM_ARRAYS - 1; i >= 0; i--) {
        counter[i]++;
        // If incrementing the current counter didn't overflow, we're good, so we break.
        if (counter[i] < maxes[i]) {
            break;
        } else {
            // Overflow by setting the counter to 0.
            counter[i] = 0;
            // Now we will fall through and move to the next counter.
        }
    }
    // Check for all 0's intelligently.  State == 0 means counter[0] is 0.
    // If it's no longer 0, move to state 1.
    if (state == 0 && counter[0] > 0) {
        state = 1;
    } else (state == 1 && counter[0] == 0) {
        break;
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

This seems to work, although I haven't tested it thoroughly. It's in python but hopefully it's clear how to use in your case. The important point is that it divides the problem up into easier parts to avoid the deeply-nested for loops.

test_arrays = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
def combine(partial, next_array):
    new_array = []
    for p in partial:
        if not isinstance(p, list):
            p = [p]
        for v in next_array:
            new_array.append(p + [v])
    return new_array

def combinations(arrays):
    base = arrays[0]
    for i in xrange(1, len(arrays)):
        base = combine(base, arrays[i])
    return base

print combinations(test_arrays)

But as others have said above, you almost certainly don't want to do this at all. A better approach would be to select random combinations and test/evaluate those. Various algorithms can be used to improve on naive random sampling, but which is appropriate depends on your application.

Improve this answer

2 Comments

Python has many, many features that make it hard to efficiently transliterate to C. In this case, the .append method particularly.
Indeed, but the python is really serving as pseudo-pseduo-code here - I hope the questioner won't just try to 'transliterate' the answer, but rather understand the reasoning behind the algorithm. Given that the approach itself is questionable, the principle seems to matter more than the practice.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.