Algorithm to find all possible solutions from an array of array

Question

What is the best algorithm to find all possible words from an array of array of character.

Here an example : From this array : [[A],[B,C,D],[E,F],[G,H]] I need in return an array of the 12 ordered possibilities [[A,B,E,G],[A,C,E,G], ... , [A,D,F,H]]

Do you know how to implement this algorithm ? If you know it and you provide an example in any language (C,JAVA,Javascript, ...), feel free to share because it's been a day I try to find it ...

Here how I tries to implement it ("array" is an array of array of char):

+ (NSArray*) possibleReading:(NSMutableArray*)array {
    int nbPossibilities = 1;
    for(int i = 0; i < [array count]; i++) {
        nbPossibilities *=[[array objectAtIndex:i] count];
    }

    NSMutableArray *possArr = [[NSMutableArray alloc] initWithCapacity:nbPossibilities];
    for (int i=0; i < nbPossibilities; i++) {
        NSMutableArray *innerArray = [[NSMutableArray alloc] initWithCapacity:[array count]];
        [possArr addObject:innerArray];
    }

    for (int i=0; i< [array count]; i++) {
        //
        for(int nbPoss = 0; nbPoss < nbPossibilities; nbPoss++) {
            NSMutableArray * arr = [possArr objectAtIndex:nbPoss];
            NSNumber * num = [NSNumber numberWithInt:nbPoss % [[array objectAtIndex:i] count]];
            NSString * literal = [[array objectAtIndex:i] objectAtIndex:[num intValue]];
            [arr insertObject:literal atIndex:i];
        }

    }
    return possArr;
}

Answer 1

It would be easiest to do this using a recursive method.

Java code

import java.util.Arrays;

public class CartesianProductCalculator {

    private char[][] result;
    private char[][] sets;
    private char[] currentSet;
    private int index;

    public char[][] calculateProduct(char[][] sets) {
        index = 0;
        // calculate size of result
        int resultSize = 1;
        this.sets = sets;
        for (char[] set : sets) {
            resultSize *= set.length;
        }
        result = new char[resultSize][];
        currentSet = new char[sets.length];
        calculateProduct(sets.length-1);
        return result;
    }

    // fills result from right to left
    public void calculateProduct(int setIndex) {
        if (setIndex >= 0) {
            for (char c : sets[setIndex]) {
                currentSet[setIndex] = c;
                calculateProduct(setIndex-1);
            }
        } else {
            result[index++] = Arrays.copyOf(currentSet, currentSet.length);
        }
    }

    public static void main(String[] args) {
        char[][] input = {{'A'},{'B','C','D'},{'E','F'},{'G','H'}};
        CartesianProductCalculator productCalculator = new CartesianProductCalculator();
        System.out.println(Arrays.deepToString(productCalculator.calculateProduct(input)));
    }
    
}

Answer 2

Objectiv-C

   + (NSArray *) cartesianProductOfArrays(NSArray *arrays) {
        int arraysCount = arrays.count;
        unsigned long resultSize = 1;
        for (NSArray *array in arrays)
            resultSize *= array.count;
        NSMutableArray *product = [NSMutableArray arrayWithCapacity:resultSize];
        for (unsigned long i = 0; i < resultSize; ++i) {
            NSMutableArray *cross = [NSMutableArray arrayWithCapacity:arraysCount];
            [product addObject:cross];
            unsigned long n = i;
            for (NSArray *array in arrays) {
                [cross addObject:[array objectAtIndex:n % array.count]];
                n /= array.count;
            }
        }
        return product;
    }

Answer 3

C

#include <stdio.h>
#include <string.h>

void print(int size, char *array[size], int indexs[size]){
    char result[size+1];
    int i;
    for(i = 0; i < size; ++i)
        result[i] = array[i][indexs[i]];
    result[size] = 0;
    puts(result);
}

int countUp(int size, int indexs[size], int lens[size]){
    int i = size -1;
    while(i >= 0){
        indexs[i] += 1;// count up
        if(indexs[i] == lens[i])
            indexs[i--] = 0;
        else
            break;
    }
    return i >= 0;
}

void find_all(int size, char *array[size]){
    int lens[size];
    int indexs[size];
    int i;

    for(i = 0; i < size; ++i){//initialize
        lens[i] = strlen(array[i]);
        indexs[i] = 0;
    }

    do{
        print(size, array, indexs);
    }while(countUp(size, indexs, lens));
}

int main(void){
    char *array[] = { "A", "BCD", "EF", "GH" };
    int size = sizeof(array)/sizeof(*array);

    find_all(size, array);
    return 0;
}

Answer 4

If you can remove duplicate entries in inner array objects before executing method then you won't get duplicate words in result array.

- (NSArray*) possibleReading:(NSMutableArray*)array {
    int nbPossibilities = 1;
    for(int i = 0; i < [array count]; i++) 
     {


        NSArray *cleanedArray = [[NSSet setWithArray:[array objectAtIndex:i]] allObjects];
        [array replaceObjectAtIndex:i withObject:cleanedArray];
         nbPossibilities *=[[array objectAtIndex:i] count];
    }

    NSMutableArray *possArr = [[NSMutableArray alloc] initWithCapacity:nbPossibilities];
    for (int i=0; i < nbPossibilities; i++) {
        NSMutableArray *innerArray = [[NSMutableArray alloc] initWithCapacity:[array count]];
        [possArr addObject:innerArray];
    }

    for (int i=0; i< [array count]; i++) {
        //
        for(int nbPoss = 0; nbPoss < nbPossibilities; nbPoss++) {
            NSMutableArray * arr = [possArr objectAtIndex:nbPoss];
            NSNumber * num = [NSNumber numberWithInt:nbPoss % [[array objectAtIndex:i] count]];
            NSString * literal = [[array objectAtIndex:i] objectAtIndex:[num intValue]];
            [arr insertObject:literal atIndex:i];
        }

    }
    return possArr;
}