Перестановки ArrayList <Integer> - PullRequest
Новая
       10

Перестановки ArrayList <Integer>

0 голосов
/ 28 апреля 2018

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

[1,2,0]

[1,0,2]

[2,0,1]

[2,1,0]

я знаю, как сделать это с 3 циклами, но дело в том, что мне нужно повторить это для разных наборов чисел с разными размерами, поэтому мне нужен один метод, который я могу применить к разным наборам чисел, но не имею понятия о том, как это сделать. Я предполагаю, что мне нужно использовать какую-то рекурсивную функцию, но я не знаю, как ее реализовать, чтобы числа не могли начинаться с 0. Есть идеи? пожалуйста, просто не публикуйте код, я хочу понять проблему, спасибо за преимущество !!

Ответы [ 2 ]

0 голосов
/ 28 апреля 2018

Любопытный вопрос! Интересный код ката.

Я наивно думаю, что у меня есть рекурсивный метод, который принимает:

  • список предметов, выбранных абонентом в данный момент
  • набор предметов, доступных для вызываемого абонента

Метод будет перебирать набор, чтобы выбрать еще 1 элемент, и вызывать себя со списком, расширенным этим элементом, и набором, уменьшенным этим элементом. После возвращения удалите из списка, добавьте обратно в набор и переходите к следующему пункту (возьмите защитную копию набора курса).

Если текущий список пуст, выбранный первый элемент не может быть 0, согласно вашим правилам. Если вам нужно где-то собрать перестановки (а не просто распечатать), для коллекции или наблюдателя потребуется третий аргумент.

Рекурсия obvioulsy прекращается, когда доступный набор пуст, после чего перестановка отправляется в коллекцию или наблюдателю.

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

Остерегайтесь, это требует глубины рекурсии N для N предметов. Но опасность минимальна, потому что даже при N = 10000 он может не быть переполнением стека, но время выполнения ЦП будет порядка (N!) (Вероятно, конец вселенной ...)

0 голосов
/ 28 апреля 2018

Вы можете решить это рекурсивно, как описано здесь: Перестановка ArrayList чисел с использованием рекурсии . Единственное, чего здесь не хватает, так это вашего ограничения нулями, которое можно решить примерно так (цикл взят из примера выше): 

for (List<Integer> al : myLists) {

    // The part you need to add:
    if (al.get(0) == 0) {
        continue;
    }

    String appender = "";
    for (Integer i : al) {
        System.out.print(appender + i);
        appender = " ";
    }
    System.out.println();
}

Вы в основном проверяете первый элемент каждой перестановки и пропускаете те, которые имеют начальный ноль. continue переходит к следующей итерации цикла и, следовательно, к следующей перестановке.

...