Есть ли метод, возвращающий все возможные комбинации, для n выберите k? - PullRequest
Новая
       10

Есть ли метод, возвращающий все возможные комбинации, для n выберите k?

0 голосов
/ 17 января 2019

Я ищу библиотечную функцию, которая возвращает любую комбинацию из n подмножеств из набора k. Например, у меня есть набор {1,2,3,4,5}, и мне нужна любая комбинация из 3 чисел, включенных в этот набор. Заказ не имеет значения. Так что эта функция должна вернуть:

[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5 ], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

Я пытался написать это сам, но безуспешно, и я сдаюсь. Это работает только тогда, когда я беру 3 номера из любого набора. Может быть, кто-то знает функцию библиотеки для этой проблемы.

Ответы [ 3 ]

0 голосов
/ 18 января 2019

Это простое и короткое решение с использованием потоков: 

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.Set;

import static java.util.stream.Collectors.toSet;

public class MakeSubsets {
  static <T> Set<Set<T>> subsets(Set<T> set, int size) {
    if (size < 1) {
      return Collections.singleton(Collections.emptySet());
    }
    return set.stream()
          .flatMap(e -> subsets(remove(set, e), size - 1).stream().map(s -> add(s, e)))
          .collect(toSet());
  }

  static <T> Set<T> add(Set<T> set, T elem) {
    Set<T> newSet = new LinkedHashSet<>(set);
    newSet.add(elem);
    return newSet;
  }

  static <T> Set<T> remove(Set<T> set, T elem) {
    Set<T> newSet = new LinkedHashSet<>(set);
    newSet.remove(elem);
    return newSet;
  }

  public static void main(String[] args) {
    Set<Integer> set = new LinkedHashSet<>(Arrays.asList(1, 2, 3, 4, 5));
    System.out.println(subsets(set, 3));
  }
}

Как это работает: метод subsets создает набор всех подмножеств заданного размера.

В случае size < 1 возвращает набор, содержащий только пустой набор.

В противном случае для каждого элемента данного набора он создает новый набор без этого выбранного элемента. Затем он создает (рекурсивно) набор подмножеств с size - 1 элементами этого меньшего набора. Затем он добавляет выбранный элемент к каждому набору в результате. Поэтому все наборы в результате имеют желаемый размер.

Рекурсия заканчивается, потому что на каждом уровне рекурсии size будет уменьшаться на единицу, что будет равным < 1.

Здесь предполагается, что set.size() >= size и size >= 0.

0 голосов
/ 18 января 2019

Я нашел здесь рекурсивное решение: https://stackoverflow.com/a/16256122/10929764 но это только распечатывает комбинации. Я попытался изменить его, чтобы он возвращал все комбинации в виде ArrayList, но он не работает. Вот код: 

public ArrayList<String[]> comb2(ArrayList<String>arr, int len, int startPosition, String[] result, ArrayList<String[]> allResults){
    if (len == 0){
        System.out.println(Arrays.toString(result));
        allResults.add(result);
        return allResults;
    }
    for (int i = startPosition; i <= arr.size()-len; i++){
        result[result.length - len] = arr.get(i);
        comb2(arr, len-1, i+1, result,allResults);
    }
    return allResults;
}

Правильно распечатывает все комбинации:

[A, B, C] [A, B, D] [A, B, E] [A, C, D] [A, C, E] [A, D, E] [B, C, D] [B, C, E] [B, D, E] [C, D, E]

но когда я распечатываю allResults, которые ранее были возвращены методом comb2, я получаю:

[C, D, E] [C, D, E] [C, D, E] [C, D, E] [C, D, E] [C, D, E] [C, D, E] [C, D, E] [C, D, E] [C, D, E]

0 голосов
/ 17 января 2019

Я не знаю никаких функций библиотеки наизусть, но вы могли бы использовать следующее решение: 

import java.io.PrintStream;
import java.util.*;

public class CombinationCalc<T> {
    private void getSubsets(List<T> input, int length, int index, Set<T> currentSet, List<Set<T>> solution) {
        if (currentSet.size() == length) {
            solution.add(new HashSet<>(currentSet));
            return;
        }
        if (index == input.size()) {
            return;
        }
        T x = input.get(index);
        currentSet.add(x);
        getSubsets(input, length, index + 1, currentSet, solution);
        currentSet.remove(x);
        getSubsets(input, length, index + 1, currentSet, solution);
    }

    public List<Set<T>> getSubsets(List<T> input, int length) {
        List<Set<T>> solution = new ArrayList<>();
        getSubsets(input, length, 0, new HashSet<>(), solution);
        return solution;
    }

    public void printSolution(List<Set<T>> solution, PrintStream ps) {
        Iterator<Set<T>> solutionIterator = solution.iterator();
        ps.print("[");
        if (!solutionIterator.hasNext()) {
            ps.print("]");
        }
        while (solutionIterator.hasNext()) {
            Set<T> solutionEntry = solutionIterator.next();
            Iterator<T> setEntry = solutionEntry.iterator();
            ps.print("[");
            if (!setEntry.hasNext()) {
                ps.print("]");
            }
            while (setEntry.hasNext()) {
                T entry = setEntry.next();
                ps.print(entry);
                if (setEntry.hasNext()) {
                    ps.print(", ");
                } else {
                    ps.print("]");
                }
            }
            if (solutionIterator.hasNext()) {
                ps.print(", ");
            } else {
                ps.print("]");
            }
        }
        ps.println();
    }


    public static void main(String[] args) {
        CombinationCalc<Integer> calc = new CombinationCalc<>();
        List<Integer> input = Arrays.asList(1, 2, 3, 4, 5);
        List<Set<Integer>> solution = calc.getSubsets(input, 3);

        calc.printSolution(solution, System.out);
    }
}

Он основан на решении .

.
...