перечислить все комбинации того, что пользователь может выбрать, на основе списка элементов из списка AC # - PullRequest
Новая
       1

перечислить все комбинации того, что пользователь может выбрать, на основе списка элементов из списка AC #

0 голосов
/ 17 марта 2012

У меня есть список в C # со следующими элементами: 

Package1
Package2
Package3
Package4
Package5
and so on...

Пользователь может выбрать несколько элементов из этого списка.Мне нужен алгоритм на c # или Java (предпочтительно на c #), который может подсказать мне все возможные варианты выбора, которые может сделать пользователь, например Package1 и Package2, Package3 и Package1, Package2, Package4 и Package 3 и т. Д.

1 Ответ

0 голосов
/ 17 марта 2012

Вы можете использовать рекурсию, «угадать», если первый пакет находится в комбинации или нет - и вызывать рекурсивно без первого пакета.

Псевдо-код: 

combinations(packages, sol):
   if (packages.length == 0): //base clause
      print sol
      return
   package <- packages.first //1 possibility: the first package is in the combination
   packages.removeFirst()
   sol.append(package) 
   combinations(packages,sol) //recursively invoke without the first package
   sol.removeLast() //clean up environment - remove the last added package
   combinations(packages,sol) //2nd possibility: the first package is not in the combination

Примечания:

  • Предполагается, что пустое решение [пакет не был выбран] также является возможным вариантом в этом алгоритме - если это не так, его можно легко обработать в предложении base.
  • Предполагается, что порядок не важен. Package1 AND Package2 - это то же самое, что Package2 AND Package1.
  • Существует 2^n возможных комбинаций для выбора пакетов, поэтому любому алгоритму, который выполняет то, что вы просите [включая этот], потребуется O(2^n) время, поэтому я бы не стал вызывать этот алгоритм с 100 пакетами ... .

В Java это может выглядеть примерно так: 

public static void printCombinations(LinkedList<String> packages, LinkedList<String> sol) {
    if (packages.size() == 0) { 
        System.out.println(sol);
        return;
    }
    String pack = packages.poll(); //also removes the head
    sol.addLast(pack);
    printCombinations(new LinkedList(packages),sol);
    sol.removeLast();
    printCombinations(new LinkedList(packages),sol);
}

и вызов по: 

printCombinations(packages, new LinkedList<String>());

Где packages - это LinkedList со всеми вашими пакетами.

  • Я использовал LinkedList для packages и создал новые объекты, потому что я найти более понятным. Для повышения производительности - вы можете использовать один массив с index [который будет изменен между рекурсивными вызовами] в чтобы не повторять packages столько раз.
...