Анализ метода генерации перестановок для JAVA - PullRequest
Новая
       14

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

0 голосов
/ 10 мая 2018

Я пытался найти время для анализа этой JAVA-программы для генерации перестановок. Я знаю в алгоритме, что сложность времени составляет O (n * n!) И O (n), потому что это требует, чтобы это напечатало перестановку. Может ли кто-то дополнительно объяснить анализ реализации ниже? 

import java.util.*;

public class Permutation
{
    public static void main(String[] args) throws Exception {

    List<Integer> intList = new ArrayList<Integer>();
    intList.add(1);
    intList.add(2);
    intList.add(3);
    List<List<Integer>> myLists = listPermutations(intList);

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

}



   public static List<List<Integer>> listPermutations(List<Integer> list) 
   {

        if (list.size() == 0) 
        {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            result.add(new ArrayList<Integer>());
            return result;
        }

        List<List<Integer>> returnMe = new ArrayList<List<Integer>>();

        Integer firstElement = list.remove(0);

        List<List<Integer>> recursiveReturn = listPermutations(list);
        for (List<Integer> li : recursiveReturn) 
        {
            for (int index = 0; index <= li.size(); index++) 
            {
                List<Integer> temp = new ArrayList<Integer>(li);
                temp.add(index, firstElement);
                returnMe.add(temp);
            }

        }
        return returnMe;
    }
}
//end Java program

1 Ответ

0 голосов
/ 10 мая 2018

Вот описание того, как это работает: 

remove the first element
get all permutations of the remaining elements (recursively)
for each position in each permutation
    insert the first element at that position in that permutation

Используя пример 

permutations of [a, b, c]
    remove a
    permutations of [b, c]
        remove b
        permutations of [c]
            remove c
            permutations of []
            = [[]]
        for each, insert c in each position
        =[[c]]
    for each, insert b in each position
    =[[b,c], [c,b]]
for each, insert a in each position
= [[a,b,c], [a,c,b], [b,a,c], [c,a,b], [b,c,a], [c,b,a]]

Для расчета перестановок для n элементов требуется вычисление перестановок для n-1 элементов (рекурсивный вызов), а затем их обработка n раз (вставки). То же самое верно для n-1 и так далее до 0, что требует постоянного времени (1). Следовательно, O - это n * n-1 * n-2 ... 1 или n!.

...