Генерация Всех Перестановок Символьных комбинаций, когда # массивов и длина каждого массива неизвестны

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

На самом деле это самое простое и понятное решение. Следующее находится в 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;
}

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

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

Затем пройдитесь циклом по всем массивам в вашем рваном массиве, создавая все необходимые вам перестановки.

Это имеет смысл?

Похоже, вы уже почти разобрались с этим.

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

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

% perm.rb ruby is cool

~ / bin / 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, но не ожидайте, что он будет работать без небольшого исправления;) Однако он работает в Maya.

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

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