Générer toutes les permutations de combinaisons de caractères lorsque le nombre de tableaux et de longueur de chaque tableau sont inconnus

EDIT STROND>: Voici une solution rubis. C'est à peu près la même chose que mon autre solution ci-dessous, mais suppose que vos matrices de caractères d'entrée sont des mots: vous pouvez donc taper: xxx pré>

~ / bin> ~ / em> p> xxx pré>

ancien strong> - J'ai un script pour le faire à Mel (la langue intégrée de Maya) - je vais essayer de traduire quelque chose de comme , mais ne vous attendez pas à ce qu'il fonctionne sans un peu de fixation;) Cela fonctionne cependant à Maya. P>

Premier - jetez tous les tableaux ensemble dans un ensemble long avec des délimiteurs. (Je vais vous laisser cela - parce que dans mon système, il déchire les valeurs d'une interface utilisateur). Ainsi, cela signifie que les délimiteurs prendront des emplacements supplémentaires: utiliser vos données d'échantillon ci-dessus: p> xxx pré>

bien sûr, vous pouvez concaténer autant de réseaux que vous le souhaitez. P >

string[] getPerms( string delimitedArray[]) {

    string result[];
    string delimiter("|");
    string compactArray[]; // will be the same as delimitedArray, but without the "|" delimiters
    int arraySizes[]; // will hold number of vals for each array
    int offsets[]; // offsets will holds the indices where each new array starts.
    int counters[]; // the values that will increment in the following loops, like pegs in each array

    int nPemutations = 1; 
    int arrSize, offset, nArrays;

    // do a prepass to find some information about the structure, and to build the compact array
    for (s in delimitedArray) {
        if (s == delimiter) { 
            nPemutations *= arrSize; // arrSize will have been counting elements 
            arraySizes[nArrays] = arrSize; 
            counters[nArrays] = 0; // reset the counter
            nArrays ++; // nArrays goes up every time we find a new array
            offsets.append(offset - arrSize) ; //its here, at the end of an array that we store the offset of this array
            arrSize=0; 
        } else { // its one of the elements, not a delimiter
            compactArray.append(s);
            arrSize++;
            offset++;
        }       
    }

    // put a bail out here if you like
    if( nPemutations > 256) error("too many permutations " + nPemutations+". max is 256");


    // now figure out the permutations
    for (p=0;p<nPemutations;p++) {
        string perm ="";

        // In each array at the position of that array's counter
        for (i=0;i<nArrays ;i++) {
            int delimitedArrayIndex = counters[i] + offsets[i] ;
            // build the string
            perm += (compactArray[delimitedArrayIndex]);

        }
        result.append(perm);

        // the interesting bit
        // increment the array counters, but in fact the program
        // will only get to increment a counter if the previous counter
        // reached the end of its array, otherwise we break
        for (i = 0; i < nArrays; ++i) {
            counters[i] += 1;
            if (counters[i] < arraySizes[i])
                break;
            counters[i] = 0;
        }
    }

    return result;
}

solution récursive

C'est en fait la solution la plus simple et la plus simple. Ce qui suit est en Java, mais il devrait être instructif: p> xxx pré>

( Voir Sortie complète ) p>

Remarque: Les tableaux Java sont basés sur 0, donc k code> va de 0..arr.length-1 code> pendant la récursivité, jusqu'à ce que k == arrs.lengthlthlengthlthlengthlthlength1. / code> Quand c'est la fin de la récursion. p>

---

solution non récursive h3>

Il est également possible d'écrire une solution non récursive, mais franchement, cela est moins intuitif. Ceci est en fait très similaire à la conversion de base, par ex. de décimale à hexadécimale; C'est une forme généralisée où chaque position a son propre ensemble de valeurs. p> xxx pré>

( Voir la sortie complète ) P>

Ceci produit les tulets dans un ordre différent. Si vous souhaitez les générer dans le même ordre que la solution récursive, vous iTerez-vous via ARRS code> "Backward" pendant décodage code> comme suit: p>

static String decode(Object[][] arrs, int v) {
    String s = "";
    for (int i = arrs.length - 1; i >= 0; i--) {
        int Ni = arrs[i].length;
        s = arrs[i][v % Ni] + s;
        v = v / Ni;
    }
    return s;
}

Merci à @polyGenLubricants pour l'excellente solution. Voici l'équivalent JavaScript:

var a=['0'];

var b=['Auto', 'Home'];

var c=['Good'];

var d=['Tommy', 'Hilfiger', '*'];

var attrs = [a, b, c, d];

function recurse (s, attrs, k) {
    if(k==attrs.length) {
        console.log(s);
    } else {
        for(var i=0; i<attrs[k].length;i++) {
            recurse(s+attrs[k][i], attrs, k+1);
        }
    } 
}
recurse('', attrs, 0);