Dato un set S, trova tutti i sottoinsiemi massimi la cui somma <= k

Question

Questa è una domanda di intervista su Facebook che ho trovato su un portale online.

Dato un set S, trovare tutti i sottoinsiemi massimi la cui somma < = k. Ad esempio, se S = {1, 2, 3, 4, 5} e k = 7 L'output è: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} { 3, 4}

consigli:

• uscita non contiene qualsiasi insieme che è un sottoinsieme di altri.
• Se X = {1, 2, 3} è una delle soluzioni allora tutti i sottoinsiemi di X {1} {2} {3} {1, 2} {1, 3} {2, 3} vengono omessi .
• L'ordine lessicografico può essere utilizzato per risolverlo.

Qualche idea come si potrebbe risolvere?

Answer 1

Ho qualche idea: hai bisogno di un albero.

Se hai immesso l'input di {1, 2, 3, 4, 5} e stai cercando i sottoinsiemi massimi, dovresti costruire un albero partendo dai numeri più grandi e sempre espandere while sum <= k (quindi non fermarti sul 4-2, ma scendere a 1 per ottenere 4-2-1).

Così, i nodi a partire dal 5 sarebbe: 5-1/5-2 - solo quelle 2 hanno somma < = 7

a partire da 4: 4-3/4- 2-1/4-1 (sottoinsieme precedente)

partire da 3: 3-2-1/3-1 (sottoinsieme precedente)

starti ng da 2: 2-1 (sottoinsieme di 3-2-1)

a partire da 1: 1 (sottoinsieme di 2-1)

Quindi è possibile ordinare le uscite valide e ottenere {1, 2, 3 } {1, 2, 4} {1, 5} {2, 5} {3, 4}

Answer 2

Questo è un problema di alimentazione. Recentemente ho trovato this website sugli algoritmi e sta dipingendo la mia immaginazione: da qui la combinazione di soluzioni powerset/combinazioni. Puoi semplicemente copiare, incollare ed eseguire il programma.

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 3

Mi dispiace per chipping in così tardi. Ma che ne dici di fare questo?

1) costruire una struttura MIN-HEAP dalla matrice data/set

2) attraversano la struttura dalla radice e mantenere sottraendo il valore nel nodo che si visita. Una volta superata la somma richiesta (curr_sum> k), invia questo percorso, fai il backtrack al genitore e prendi un altro percorso (questo può essere fatto in modo ricorsivo).

3) Se il backtracking riporta al nodo originale da cui è stato avviato, implementare l'intero algoritmo in modo ricorsivo dal nodo root-> left.

4) Eseguire gli stessi due passaggi (2) e (3) sopra ma con un MAX-HEAP ora.

Sono nuovo agli algoritmi e alle strutture dati e ho appena iniziato a leggere Intro su Algos-Cormen. Questa potrebbe essere una soluzione difettosa, ma sarei più che felice se qualcuno mi fa notare la colpa :)

Answer 4

So che è tardi per rispondere, ma penso di aver trovato una soluzione semplice per questo problema. Enumeriamo sottoinsiemi di S in ordine lessicografico utilizzando backtracking e controllare il sum di sottoinsieme generato finora.

Quando il numero sum supera k, la parte interessante arriva: dobbiamo verificare se lo subset generato è un sottoinsieme appropriato di elementi precedentemente segnalati.

Una soluzione consiste nel mantenere tutti i sottoinsiemi segnalati e verificare l'inclusione, ma è uno spreco.

Invece, calcoliamo la differenza tra e sum. Se esiste un elemento e in S tale che e not in subset e e <= (k - sum), il set che abbiamo generato è un sottoinsieme appropriato di un sottoinsieme precedentemente segnalato e possiamo saltarlo tranquillamente.

Ecco il programma di lavoro completo in pianura vecchio C++, dimostrando l'idea:

#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; 
} 

L'uscita è tutti i sottoinsiemi massimi in ordine lessicografico, uno per riga:

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

Answer 5

una vecchia questione ma ancora interessante.

Ecco una soluzione Java 8 ricorsiva, con un approccio "permutazionale".

Ottimizzato per codice più pulito e più corto piuttosto che per le prestazioni, ad esempio lo smistamento e la potatura devono essere effettuati solo una volta.

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()); 
    } 
} 

per controllo:

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

Answer 6

algoritmo è il seguente:

• partire dal sottoinsieme vuoto.
• Esegue il ciclo attraverso la matrice originale dall'inizio (supponendo che la matrice sia già ordinata in ordine crescente) finché currentSum non è uguale o inferiore alla somma di destinazione.
• Se l'elemento corrente aggiunto a currentSum è inferiore alla somma della destinazione, si aggiunge all'elemento corrente subSet corrente e si esegue la ricorsione a partire dall'elemento successivo.
• Interruzione del ciclo corrente se la somma corrente supera targetSum.
• Se non è possibile aggiungere più elementi nel sottoset corrente, controlliamo se è massimo e lo stampiamo in questo caso.
• Per determinare i sottoinsiemi massimi possiamo confrontare l'array originale e il sottosetario corrente elemento per elemento, cercando la prima mancata corrispondenza.Se l'elemento al primo indice di disallineamento è maggiore della differenza tra currentSum e targetSum, subSet è massimo e deve essere stampato.

Soluzione di lavoro su Java è qui sotto:

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} 
    } 

}