Для заданного множества S найти все максимальные подмножества, у которых сумма <= k

Question

Это вопрос интервью на Facebook, с которым я столкнулся на онлайн-портале.

Для заданного множества S найти все максимальные подмножества, сумма которых <= k. Например, если S = ​​{1, 2, 3, 4, 5} и k = 7 Выходные данные: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4} </p>

Советы:

• Вывод не содержит никакого набора, который является подмножеством другого.
• Если X = {1, 2, 3} является одним из решений, то все подмножества X {1} {2} {3} {1, 2} {1, 3} {2, 3} опущены .
• Для ее решения можно использовать лексикографический порядок.

Есть идеи, как это можно решить?

Answer 1

У меня есть идея - вам нужно дерево.

Если вы ввели {1, 2, 3, 4, 5} и ищете максимальные подмножества - вы должны построить дерево, начиная с самых больших чисел, ивсегда расширяйте while sum <= k (поэтому не останавливайтесь на 4-2, а уменьшитесь до 1, чтобы получить 4-2-1).

Итак, узлы, начинающиеся с 5, будут: 5-1 / 5-2 - только те 2 имеют сумму <= 7 </p>

начиная с 4: 4-3 / 4-2-1 / 4-1 (подмножество предыдущего)

начиная с 3: 3-2-1 / 3-1 (подмножество предыдущего)

запускот 2: 2-1 (подмножество 3-2-1)

начиная с 1: 1 (подмножество 2-1)

Затем вы можете отсортировать допустимые результаты и получить {1,2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}

Answer 2

Я знаю, что уже поздно отвечать, но я думаю, что нашел простое решение этой проблемы.Мы перечисляем подмножества S в лексикографическом порядке с использованием обратного отслеживания и проверяем sum подмножества, сгенерированного до сих пор.

Когда sum превышает k, возникает интересная часть: нам нужно проверить,сгенерированный subset является правильным подмножеством ранее сообщенных элементов.

Одним из решений является сохранение всех зарегистрированных подмножеств и проверка на включение, но это расточительно.

Вместо этого мы вычисляем разницумежду k и sum.Если в S есть элемент e, такой что e not in subset и e <= (k - sum), то сгенерированный нами набор является правильным подмножеством ранее сообщенного подмножества, и мы можем спокойно его пропустить.

Вот полная рабочая программа на старом простом C ++, демонстрирующая идею:

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

typedef std::set<int> Set;
typedef std::vector<int> SubSet;

bool seen_before(const Set &universe, const SubSet &subset, int diff) {
    Set::const_iterator i = std::mismatch(universe.begin(), universe.end(),
                                          subset.begin()).first;
    return i != universe.end() && *i <= diff;
}

void process(const SubSet &subset) {
    if (subset.empty()) {
        std::cout << "{}\n";
        return;
    }
    std::cout << "{" << subset.front();
    for (SubSet::const_iterator i = subset.begin() + 1, e = subset.end();
         i != e; ++i) {
        std::cout << ", " << *i;
    }
    std::cout << "}\n";
}

void generate_max_subsets_rec(const Set &universe, SubSet &subset,
                              long sum, long k) {
    Set::const_iterator i = subset.empty()
        ? universe.begin()
        : universe.upper_bound(subset.back()),
        e = universe.end();
    if (i == e) {
        if (!seen_before(universe, subset, k - sum))
            process(subset);
        return;
    }
    for (; i != e; ++i) {
        long new_sum = sum + *i;
        if (new_sum > k) {
            if (!seen_before(universe, subset, int(k - sum)))
                process(subset);
            return;
        } else {
            subset.push_back(*i);
            if (new_sum == k)
                process(subset);
            else
                generate_max_subsets_rec(universe, subset, new_sum, k);
            subset.pop_back();
        }
    }
}

void generate_max_subsets(const Set &universe, long k) {
    SubSet subset;
    subset.reserve(universe.size());
    generate_max_subsets_rec(universe, subset, 0, k);
}

int main() {
    int items[] = {1, 2, 3, 4, 5};
    Set u(items, items + (sizeof items / sizeof items[0]));
    generate_max_subsets(u, 7);
    return 0;
}

Вывод всех максимальных подмножеств в лексикографическом порядке, по одному на строку:

{1, 2, 3}
{1, 2, 4}
{1, 5}
{2, 5}
{3, 4}

Answer 3

Алгоритм следующий:

• Начиная с пустого подмножества.
• Цикл по исходному массиву с начала (при условии, что массив уже отсортирован в порядке возрастания), пока значение currentSum не станет меньше илиравна целевой сумме.
• Если текущий элемент, добавленный к currentSum, меньше целевой суммы, добавление к текущему текущему элементу подсети и запуск рекурсии, начиная со следующего элемента.
• Прерывание текущего цикла, если текущая сумма превышаетtargetSum.
• Если мы не можем добавить больше элементов в текущий поднабор, мы проверяем, является ли он максимальным , и печатаем его в этом случае.
• Чтобы определить максимальные подмножества, мыможет сравнивать исходный массив и текущий элемент subSet по элементам, ища первое несоответствие.Если индекс первого несоответствия элемента больше, чем разница между currentSum и targetSum, subSet максимален и должен быть напечатан.

Рабочее решение на Java ниже:

public class Test {

    /**
     * Assuming alphabet[] is already sorted in increasing order
     */
    public static void printMaximalSubSetsToSum(int[] alphabet, int sum) {
        if (alphabet == null || alphabet.length == 0) {
            return;
        }
        if (alphabet[0] > sum) {
            // no sense to search, since smallest element in array already bigger than sum
            return;
        } else if (alphabet[0] == sum) {
            Set<Integer> subSet = new HashSet<>();
            subSet.add(alphabet[0]);
            printSubset(subSet);
        }
        Set<Integer> subSet = new HashSet<>();
        processMaximalSubSetToSum(alphabet, sum, 0, 0, subSet);
    }

    private static void processMaximalSubSetToSum(int[] alphabet, int sum, int sumSoFar, int startFrom, Set<Integer> subSet) {
        if (startFrom >= alphabet.length) {
            if (isMaximalSubSet(alphabet, subSet, sum - sumSoFar)) {
                printSubset(subSet);
            }
            return;
        }
        for (int i = startFrom; i < alphabet.length; i++) {
            int newSum = sumSoFar + alphabet[i];
            if (newSum > sum) {
                if (isMaximalSubSet(alphabet, subSet, sum - sumSoFar)) {
                    printSubset(subSet);
                }
                return;
            } else {
                subSet.add(alphabet[i]);
                if (newSum == sum) {
                    printSubset(subSet);
                } else {
                    processMaximalSubSetToSum(alphabet, sum, newSum, i + 1, subSet);
                }
                subSet.remove(alphabet[i]);
            }
        }
    }

    private static boolean isMaximalSubSet(int[] alphabet, Set<Integer> subSet, int diff) {
        // search first mismatch element between alphabet and current SubSet
        Iterator<Integer> it = subSet.iterator();
        int i = 0;
        while (it.hasNext()) {
            if (it.next() != alphabet[i]) {
                break;
            }
            i++;
        }
        return i >= alphabet.length || alphabet[i] > diff;
    }

    private static void printSubset(Set<Integer> subset) {
        System.out.println(subset);
    }

    public static void main(String[] args) throws java.lang.Exception {
        //printMaximalSubSetsToSum(new int[]{1, 2, 3, 4, 5}, 7);
        // Correct output is: {1, 2, 3}; {1, 2, 4}; {1, 5}; {2, 5}; {3, 4}
    }

}

Answer 4

Старый вопрос, но все еще интересный.

Вот рекурсивное решение Java 8 с "перестановочным" подходом.

Оптимизирован для более чистого и короткого кода, а не производительности - например, сортировка и сокращение должны выполняться только один раз.

import com.google.common.collect.ImmutableList;
import com.google.common.collect.Ordering;
import java.util.*;
import java.util.stream.Collectors;

public class SubsetFinder {
    public List<List<Integer>> findSubsets(List<Integer> input, int k) {
        List<List<Integer>> listOfLists = new ArrayList<>();
        List<Integer> copy = Ordering.natural().sortedCopy(input);

        while (!copy.isEmpty()) {
            int v = copy.remove(copy.size() - 1);
            if (v == k || (copy.isEmpty() && v <= k)) {
                // No need to look for subsets if the element itself == k, or
                // if it's the last remaining element and <= k.
                listOfLists.add(new ArrayList<>(Arrays.asList(v)));
            } else if (v < k) {
                findSubsets(copy, k - v).forEach(subList -> {
                    subList.add(v);
                    listOfLists.add(subList);
                });
            }
        }

        // Prune sets which are duplicates or subsets of other sets
        return listOfLists.stream().filter(
                candidate -> listOfLists.stream().noneMatch(
                        lol -> candidate != lol && lol.containsAll(candidate)
                )
        ).collect(Collectors.toList());
    }
}

Чтобы проверить это:

public static void main(String[] args) {
    new SubsetFinder()
        .findSubsets(ImmutableList.of(1, 2, 3, 4, 5), 7)
        .forEach(System.out::println);
}

Answer 5

Это проблема с питанием. Недавно я обнаружил этот веб-сайт об алгоритмах, и это поразило мое воображение: отсюда и решение по схеме питания / комбинациям. Вы можете просто скопировать, вставить и запустить программу.

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

public class Solution {
  public static void maximalSubset
    (int sum, int[] set, int choose,List<Integer[]> exclusion) {
    if(1>choose) return;
    int combinationSize = combinationSize(set.length,choose);
    int index[]=new int[choose];
    Integer subSet[] = new Integer[choose];
    for(int i=0; i<choose;i++)
      index[i]=i;
    for(int i=0; i<combinationSize; i++) {
      if(i!=0)
            nextCombination(index,set.length);
        for(int x=0; x<choose; x++)
            subSet[x]=set[index[x]];
        if(summation(sum,subSet) && !excluded(subSet,exclusion)) {
                System.out.println(Arrays.toString(subSet));
                exclusion.add(Arrays.copyOf(subSet,subSet.length));
        }
    }
    maximalSubset(sum,set,choose-1,exclusion);
}//

private static int combinationSize(int n, int r) {
    int den,limit;
    if(r>n-r) {
        den=n-r;
        limit=r;
    }else {
        den=r;
        limit=n-r;
    }
    long result=1;
    for(int i=n; i>limit;i--)
        result*=i;
    for(int i=2; i<=den;i++)
        result/=i;
    return (int)result;
}//
private static void nextCombination(int[] A, int n) {
    int c=A.length;
    int i=c-1;
    while(n-c+i==A[i])
        i--;
    A[i]++;
    for(int j=i; j<c; j++)
        A[j]=A[i]+j-i;
}//

private static boolean summation(int sum, Integer[] S) {
    for(int i:S)
        sum-=i;
    return sum>=0;
}//

private static boolean excluded(Integer[] needle,List<Integer[]> haystack) {

    for(Integer[] H: haystack) {
        int count=0;
        for(int h: H)
            for(int n:needle)
                if(h==n) {
                    count++;
                    break;//it's a set
                }
        if(count==needle.length)
            return true;
    }
    return false;
}//

public static void main(String[] args) {
    int[] S = {1, 2, 3, 4, 5};
    int k = 7;
    List<Integer[]> exclusion = new ArrayList<Integer[]>();
    maximalSubset(k,S,S.length,exclusion);
}
}

Answer 6

Прошу прощения за участие в столь позднем.Но как насчет этого?

1) Создайте структуру MIN-HEAP из заданного массива / набора

2) просмотрите структуру из корня и продолжайте вычитать значение в узле, который вы посещаете.Когда вы превысите требуемую сумму (curr_sum> k), выведите этот путь, вернитесь назад к родителю и выберите другой путь (это можно сделать рекурсивно).

3) Если при возврате назад вы вернетесь к исходному узлу, которыйВы начали с того, чтобы реализовать весь алгоритм рекурсивно из корневого узла> левого узла.

4) Выполните те же два шага (2) и (3) выше, но с MAX-HEAP сейчас.

Я новичок в алгоритмах и структурах данных, и только начал читать Вступление в Algos-Cormen.Это может быть ошибочным решением, но я был бы более чем рад, если бы кто-нибудь указал мне на ошибку :)