SORU
3 Kasım 2009, Salı


Java bir set almak bir powerset

{1, 2, 3} powerset

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}

Hadi Java Set ki:

Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set<Set<Integer>> powerSet = getPowerset(mySet);

Nasıl işlev getPowerset, karmaşıklığı mümkün olan en iyi düzeni ile yazılır? (O(2^n) olabileceğini düşünüyorum.)

CEVAP
3 Kasım 2009, Salı


Evet, O(2^n) nitekim oluşturmak için gereken bu yana, iyi, 2^n olası kombinasyonlar. Burada çalışan bir uygulama, jenerik ve ayarlar kullanarak:

public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
    Set<Set<T>> sets = new HashSet<Set<T>>();
    if (originalSet.isEmpty()) {
    	sets.add(new HashSet<T>());
    	return sets;
    }
    List<T> list = new ArrayList<T>(originalSet);
    T head = list.get(0);
    Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
    for (Set<T> set : powerSet(rest)) {
    	Set<T> newSet = new HashSet<T>();
    	newSet.add(head);
    	newSet.addAll(set);
    	sets.add(newSet);
    	sets.add(set);
    }		
    return sets;
}

Ve bir test, örnek giriş verilir

 Set<Integer> mySet = new HashSet<Integer>();
 mySet.add(1);
 mySet.add(2);
 mySet.add(3);
 for (Set<Integer> s : SetUtils.powerSet(mySet)) {
     System.out.println(s);
 }

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • GoogleTechTalks

    GoogleTechTa

    15 AĞUSTOS 2007
  • khloe brooks

    khloe brooks

    25 Temmuz 2011
  • michellefeng's channel

    michellefeng

    26 Kasım 2006