Дубли при перестановках из n элеметов

Question

Начинаю разбираться с java, но столкнулся с такой проблемой. Дана задача найти максимальное сумму из n количества элементов <= k. За неимением опыта решил всё это дело решить перестановками(предполагаю есть решение и грациозней, но теперь есть желание сделать так ради интереса).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BestTravel {
public static void main(String[] args) {
    System.out.println(chooseBestSum(163, 3, Arrays.asList(50, 55, 56, 57, 58)));
}

public static Integer chooseBestSum(int t, int k, List<Integer> ls) {
    if (ls.size() < k){
        return null;
    }
    List<Integer> list = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> index = new ArrayList<>();
    for (int i = 0; i < ls.size(); i++){
        list.add(ls.get(i));
        index.add(i);
        permutation(result, list, index, ls, k);
        list.clear();
        index.clear();
    }
    int max = 0;
    for (List<Integer> list1: result){
        int temp = list1.stream().reduce((a, b) -> a+b).get();
        System.out.println(list1);
        if(temp > max){
            if (temp <= t) max = temp;
        }
    }
    return max;
}
public static void permutation(List<List<Integer>> result, List<Integer> list, List<Integer> index,List<Integer> elem, int count){
    if(list.size() == count){
        List<Integer> list1 = new ArrayList<>(list);
        result.add(list1);
        list.remove((int)count -1);
        index.remove((int)count -1);
    } else {
        for (int i = 0; i < elem.size(); i++){
            if(!index.contains(i)){
                list.add(elem.get(i));
                index.add(i);
                permutation(result, list, index, elem, count);
            }
        }
    }
}

Задача решается, но столкнулся с проблемой, что появляются дубли при перестановках:

[50, 55, 56]
[50, 55, 57]
[50, 55, 58]
[50, 55, 56]
[50, 55, 57]
[50, 55, 58]
[55, 50, 56]
[55, 50, 57]
[55, 50, 58]
[55, 50, 56]
[55, 50, 57]
[55, 50, 58]
[56, 50, 55]
[56, 50, 57]
[56, 50, 58]
[56, 50, 55]
[56, 50, 57]
[56, 50, 58]
[57, 50, 55]
[57, 50, 56]
[57, 50, 58]
[57, 50, 55]
[57, 50, 56]
[57, 50, 58]
[58, 50, 55]
[58, 50, 56]
[58, 50, 57]
[58, 50, 55]
[58, 50, 56]
[58, 50, 57]

Подскажите, что я делаю не так и почему появились дубли?

Answer 1

Дубликаты получаются как раз из-за попытки использовать перестановки, тогда как в данном случае следовало строить список комбинаций по k элементов из заданного набора/списка значений, в данном случае их число составит:

C(5,3) = 5! / ((5 - 3)! * 3!) = 10

Для генерации комбинаций можно использовать такой рекурсивный алгоритм:

public static List<List<Integer>>combinations(List<Integer> src, List<Integer> comb, int size) {
    List<List<Integer>> result = new ArrayList<>();
    if (comb.size() == size) { // комбинация построена, выход
        result.add(comb);
    } else {
        Iterator<Integer> it = src.iterator();
        while (it.hasNext()) {
            // берем текущий элемент из списка значений
            Integer item = it.next();
            it.remove(); // удаляем его, чтобы не было повторов
    
            // создаём новую комбинацию из текущей
            List<Integer> newComb = new ArrayList<>(comb);
            newComb.add(item); // добавляем текущий элемент
            // добавляем все комбинации в результирующий список
            result.addAll(combinations(new ArrayList<>(src), newComb, size));
        }
    }
    return result;    
}

Тогда поиск суммы может быть переписан:

public static Integer bestSum(int t, int k, List<Integer> ls) {
    if (ls.size() < k) {
        return null;
    }
    List<List<Integer>> combinations = combinations(new ArrayList<>(ls), new ArrayList<>(), k);
    System.out.println("combinations size=" + combinations.size());
    int max = 0;
    for (List<Integer> comb: combinations) {
        int sum = comb.stream().mapToInt(Integer::intValue).sum();
        System.out.println(comb + " -> " + sum);
        if (sum > max) {
            if (sum <= t) {
                max = sum;
                if (max == t) {
                    break;
                }
            }
        }
    }
    return max;
}

Тест:

System.out.println("best = " + bestSum(163, 3, Arrays.asList(50, 55, 56, 57, 58)));

combinations size=10
[50, 55, 56] -> 161
[50, 55, 57] -> 162
[50, 55, 58] -> 163
best = 163

БЛОГ НА HUSL

Дубли при перестановках из n элеметов

Ответы (1 шт):