Алгоритм для создания всех перестановок и длин

Question

Я хочу создать алгоритм предпочтительно на Java. Я хотел бы go через следующий массив символов и создать из него все возможные перестановки и длины.

Например, l oop и напечатайте следующее:

a
aa
aaaa
aaaaa
.... keep going ....
aaaaaaaaaaaaaaaaa ....
ab
aba
abaa .............

Пока я не выберу все возможные длины и перестановки из моего массива.

private void method(){
    char[] data = "abcdefghiABCDEFGHI0123456789".toCharArray();
    // loop and print each time
}

Я думаю было бы глупо придумать для этого 10 циклов for. Я предполагаю, что здесь поможет какая-то форма рекурсии, но даже не могу обойтись без головы. Могу я получить помощь с этим, пожалуйста? Даже если укажет мне на начало или блог или что-то в этом роде. Погуглил и осмотрелся, и существует множество примеров перестановок, но сохраняется фиксированная максимальная длина. Похоже, что ни у кого нет примеров с несколькими перестановками длины +. Пожалуйста посоветуй. Спасибо.

Answer 1

private void method(){
    char[] data = "abcdefghiABCDEFGHI0123456789".toCharArray();
    // loop and print each time
}

С вашим заданным вводом существует 3.43731350804×10E40 комбинаций. (Результат написан словами eighteen quadrillion fourteen trillion three hundred ninety-eight billion five hundred nine million four hundred eighty-one thousand nine hundred eighty-four.) Если я правильно помню, математика - это как

1  +  x  +  x^2  +  x^3  +  x^4  +  ...  +  x^n = (1 - x^n+1) / (1 - x)

в вашем случае

28 + 28^2 + 28^3 + .... 28^28

, потому что у вас будет

28 комбинаций для строк длиной один

28 * 28 комбинаций для строк длиной два

28 * 28 * 28 комбинаций для строк длиной три

...

28 ^ 28 комбинаций для строк длиной 28

Чтобы распечатать их все, потребуется время.

Один из способов, который я могу придумать, - это использовать библиотеку Generex, Java библиотеку для генерации String, соответствующей заданному регулярному выражению.

Generex github . Дополнительную информацию см. На их странице.

Generex maven repo . Загрузите jar-файл или добавьте зависимость.

Использование generex несложно, если вы каким-то образом знакомы с регулярным выражением.

Пример с использованием только первых 5 символов, которые будут иметь 3905 возможных комбинаций

public static void main(String[] args) {
    Generex generex = new Generex("[a-e]{1,5}");
    System.out.println(generex.getAllMatchedStrings().size());
    Iterator iterator = generex.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}

Значение [a-e]{1,5} любая комбинация символов a, b, c, d, e wit минимальная длина 1 и максимальная длина 5

вывод

a
aa
aaa
aaaa
aaaaa
aaaab
aaaac
aaaad
aaaae
aaab
aaaba
aaabb
aaabc
aaabd
aaabe
aaac
....
eeee
eeeea
eeeeb
eeeec
eeeed
eeeee

Answer 2

Другой способ сделать это:

public class HelloWorld{
    public static String[] method(char[] arr, int length) {
      if(length == arr.length - 1) {
        String[] strArr = new String[arr.length];

        for(int i = 0; i < arr.length; i ++) {
            strArr[i] = String.valueOf(arr[i]);
        }

        return strArr;
      }


      String[] before = method(arr, length + 1);
      String[] newArr = new String[arr.length * before.length];
      for(int i = 0; i < arr.length; i ++) {
        for(int j = 0; j < before.length; j ++) {
          if(i == 0)
            System.out.println(before[j]);

          newArr[i * before.length + j] = (arr[i] + before[j]);
        }
      }

      return newArr;
    }

    public static void main(String []args){
        String[] all = method("abcde".toCharArray(), 0);

        for(int i = 0; i < all.length; i ++) {
          System.out.println(all[i]);
        }
    }
}

Однако будьте осторожны, у вас, вероятно, закончится память, иначе программа будет скомпилирована / запущена очень долго, если это вообще произойдет. Вы пытаетесь напечатать 3,437313508041091e + 40 строк, это 3, за которыми следуют 40 нулей.

Вот решение также в javascript, потому что он запускается, но ему нужно 4 секунды, чтобы добраться до 4-х символьных перестановок, для него для достижения 5 символьных перестановок потребуется примерно 28 раз больше, для 6 символов это 4 * 28 * 28 и т. д.

const method = (arr, length) => {
  if(length === arr.length - 1)
    return arr;

  const hm = [];
  const before = method(arr, length + 1);
  for(let i = 0; i < arr.length; i ++) {
    for(let j = 0; j < before.length; j ++) {
      if(i === 0)
        console.log(before[j]);

      hm.push(arr[i] + before[j]);
    }
  }

  return hm;
};

method('abcdefghiABCDEFGHI0123456789'.split(''), 0).forEach(a => console.log(a));

Answer 3

Для входной строки длиной 28 символов этот метод никогда не закончится, но для меньших входных данных он будет генерировать все перестановки до длины n, где n - количество символов. Сначала он печатает все перестановки длины 1, затем всю длину 2 et c, что отличается от вашего примера, но, надеюсь, порядок не имеет значения.

static void permutations(char[] arr)
{
    int[] idx = new int[arr.length];
    char[] perm = new char[arr.length];

    Arrays.fill(perm, arr[0]);

    for (int i = 1; i < arr.length; i++)
    {
        while (true)
        {
            System.out.println(new String(perm, 0, i));

            int k = i - 1;
            for (; k >= 0; k--)
            {
                idx[k] += 1;
                if (idx[k] < arr.length)
                {
                    perm[k] = arr[idx[k]];
                    break;
                }
                idx[k] = 0;
                perm[k] = arr[idx[k]];
            }
            if (k < 0)
                break;
        }
    }
}

Тест:

permutations("abc".toCharArray());

Вывод:

a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc

Answer 4

Это то, о чем вы говорите?

public class PrintPermutations
{
    public static String stream = "";

    public static void printPermutations (char[] set, int count, int length)
    {
        if (count < length)
            for (int i = 0; i < set.length; ++i)
            {
                stream += set[i];
                System.out.println (stream);

                printPermutations (set, count + 1, length);
                stream = stream.substring (0, stream.length() - 1);
            }
    }

    public static void main (String[] args)
    {
        char[] set = "abcdefghiABCDEFGHI0123456789".toCharArray();
        printPermutations (set, 0, set.length);
    }
}

Сначала проверьте это, используя меньшую строку.

Answer 5

Думаю, вашу проблему может решить следующая рекурсия:

  public static void main(String[] args) {
    final String[] data = {"a", "b", "c"};
    sampleWithReplacement(data, "", 1, 5);
  }

  private static void sampleWithReplacement(
      final String[] letters,
      final String prefix,
      final int currentLength,
      final int maxLength
  ) {
    if (currentLength <= maxLength) {
      for (String letter : letters) {
        final String newPrefix = prefix + letter;
        System.out.println(newPrefix);
        sampleWithReplacement(letters, newPrefix, currentLength + 1, maxLength);
      }

    }
  }

где data указывает возможные символы для выборки.

Answer 6

Вы можете иметь for l oop, который начинается с 1 и заканчивается на array.length, и на каждой итерации вызывает функцию, которая печатает все перестановки для этой длины.

public void printPermutations(char[] array, int length) {
  /*
   * Create all permutations with length = length and print them
   */
}

public void method() {
  char data = "abcdefghiABCDEFGHI0123456789".toCharArray();

  for(int i = 1; i <= data.length; i ++) {
    printPermutations(data, i);
  }
}