Генерация всех перестановок комбинаций символов, когда число массивов и длина каждого массива неизвестны

Question

Я не уверен, как задать свой вопрос лаконично, поэтому я начну с примеров и продолжу оттуда. Я работаю с VBA, но я думаю, что эта проблема не зависит от языка и потребует только умного подхода, который может обеспечить структуру псевдокода. Заранее спасибо за помощь!

Пример: У меня есть 3 массива символов, такие как:

Arr_1 = [X,Y,Z] 
Arr_2 = [A,B]
Arr_3 = [1,2,3,4]

Я хотел бы сгенерировать ВСЕ возможные перестановки массивов символов следующим образом:

XA1
XA2
XA3
XA4
XB1
XB2
XB3
XB4
YA1
YA2
.
.
.
ZB3
ZB4

Эту проблему легко решить, используя 3 цикла while или for loop. Мой вопрос: как мне решить эту проблему, если число массивов неизвестно и длина каждого массива неизвестна?

Так, например, с 4 символьными массивами:

Arr_1 = [X,Y,Z]
Arr_2 = [A,B]
Arr_3 = [1,2,3,4]
Arr_4 = [a,b]

Мне нужно сгенерировать:

XA1a
XA1b
XA2a
XA2b
XA3a
XA3b
XA4a
XA4b
.
.
.
ZB4a
ZB4b  

Таким образом, обобщенный пример будет:

Arr_1 = [...]
Arr_2 = [...]
Arr_3 = [...]
.
.
.
Arr_x = [...]

Есть ли способ структурировать функцию, которая будет генерировать неизвестное число циклов и проходить по длине каждого массива для генерации перестановок? Или, может быть, есть лучший способ думать о проблеме?

Спасибо всем!

Answer 1

Рекурсивное решение

Это на самом деле самое простое, простое решение. Следующее на Java, но это должно быть поучительно:

public class Main {
    public static void main(String[] args) {
        Object[][] arrs = {
            { "X", "Y", "Z" },
            { "A", "B" },
            { "1", "2" },
        };
        recurse("", arrs, 0);
    }
    static void recurse (String s, Object[][] arrs, int k) {
        if (k == arrs.length) {
            System.out.println(s);
        } else {
            for (Object o : arrs[k]) {
                recurse(s + o, arrs, k + 1);
            }
        }
    }
}

( см. Полный вывод )

Примечание: Java-массивы основаны на 0, поэтому k идет от 0..arrs.length-1 во время рекурсии до k == arrs.length, когда это конец рекурсии.

---

нерекурсивное решение

Можно также написать нерекурсивное решение, но, честно говоря, оно менее интуитивно понятно. Это на самом деле очень похоже на базовое преобразование, например, от десятичного до шестнадцатеричного; это обобщенная форма, где каждая позиция имеет свой собственный набор значений.

public class Main {
    public static void main(String[] args) {
        Object[][] arrs = {
            { "X", "Y", "Z" },
            { "A", "B" },
            { "1", "2" },
        };
        int N = 1;
        for (Object[] arr : arrs) {
            N = N * arr.length;
        }
        for (int v = 0; v < N; v++) {
            System.out.println(decode(arrs, v));
        }
    }
    static String decode(Object[][] arrs, int v) {
        String s = "";
        for (Object[] arr : arrs) {
            int M = arr.length;
            s = s + arr[v % M];
            v = v / M;
        }
        return s;
    }
}

( см. Полный вывод )

Это производит кортежи в другом порядке. Если вы хотите сгенерировать их в том же порядке, что и рекурсивное решение, то вы итерируете arrs «назад» в течение decode следующим образом:

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;
}

( см. Полный вывод )

Answer 2

Спасибо @polygenelubricants за отличное решение. Вот эквивалент 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);

Answer 3

РЕДАКТИРОВАТЬ : Вот решение рубина. Это почти то же самое, что и мое другое решение ниже, но предполагается, что ваши входные массивы символов состоят из слов: так что вы можете набрать:

% perm.rb ruby is cool

~ / бен / perm.rb

#!/usr/bin/env ruby

def perm(args)
  peg = Hash[args.collect {|v| [v,0]}]

  nperms= 1
  args.each { |a| nperms  *=  a.length }

  perms = Array.new(nperms, "")

  nperms.times do |p|
    args.each { |a| perms[p] += a[peg[a]] }

    args.each do |a|
      peg[a] += 1
      break  if peg[a] < a.length
      peg[a] = 0
    end

  end
  perms
end

puts perm ARGV

OLD - у меня есть скрипт для этого в MEL (встроенный язык Maya) - я постараюсь перевести на что-то вроде C, но не ожидаю, что он будет работать без исправление;) Это работает в майя, хотя.

Первый - выбросить все массивы в один длинный массив с разделителями. (Я оставлю это вам - потому что в моей системе это вырывает значения из пользовательского интерфейса). Таким образом, это означает, что разделители будут занимать дополнительные слоты: Чтобы использовать приведенные выше примеры данных:

 string delimitedArray[] = {"X","Y","Z","|","A","B","|","1","2","3","4","|"};

Конечно, вы можете объединять столько массивов, сколько хотите.

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;
}

Answer 4

звучит так, как будто вы уже поняли это.

Что если вы поместите туда еще один массив, назовите его, скажем, ArrayHolder, который содержит все ваше неизвестное количество массивов неизвестной длины. Тогда вам просто нужен еще один цикл, нет?

Answer 5

Если я правильно понимаю вопрос, думаю, вы могли бы поместить все свои массивы в другой массив, создавая таким образом зубчатый массив.

Затем переберите все массивы в вашем зубчатом массиве, создавая все необходимые перестановки.

Имеет ли это смысл?