JAVA：產生功率3和最大

Question

一切都在標題..之間子長度設定=）

欲快速度創建冪，只用3（最小恆定長度之間長度的子集）和最大。這個最大值應該是5的大部分時間，但我希望它是可變的（從3到5,6）。 原始設定可能較大。我需要存儲這些子集進行進一步處理。

我見過Obtaining a powerset of a set in Java，但這裏他們產生了功率集的每個子集。 我也見過efficient powerset algorithm for subsets of minimal length，對於C＃，但我認爲，正如Adam S所說，我會遇到低運行時間的性能和內存問題。

我想將這些想法合併爲一個理想的目標。我最後的希望將快速度（也許在Guava算法）生成每一個子集，並遍歷採取只與所需的長度......但即使讀它的醜陋;）

任何人有想法？

Answer 1

我從st0le的answer大量借了。

基本上，當我迭代控制集合生成的位數組時，我檢查以確保位數在最小值和最大值之間。

這是代碼。

import java.util.BitSet; 
import java.util.Iterator; 
import java.util.Set; 
import java.util.TreeSet; 

public class PowerSet<E> implements Iterator<Set<E>>, Iterable<Set<E>> { 
    private int  minSize; 
    private int  maxSize; 
    private E[]  arr  = null; 
    private BitSet bset = null; 

    @SuppressWarnings("unchecked") 
    public PowerSet(Set<E> set, int minSize, int maxSize) { 
     this.minSize = Math.min(minSize, set.size()); 
     this.maxSize = Math.min(maxSize, set.size()); 

     arr = (E[]) set.toArray(); 
     bset = new BitSet(arr.length + 1); 

     for (int i = 0; i < minSize; i++) { 
      bset.set(i); 
     } 
    } 

    @Override 
    public boolean hasNext() { 
     return !bset.get(arr.length); 
    } 

    @Override 
    public Set<E> next() { 
     Set<E> returnSet = new TreeSet<E>(); 
     // System.out.println(printBitSet()); 
     for (int i = 0; i < arr.length; i++) { 
      if (bset.get(i)) { 
       returnSet.add(arr[i]); 
      } 
     } 

     int count; 
     do { 
      incrementBitSet(); 
      count = countBitSet(); 
     } while ((count < minSize) || (count > maxSize)); 

     // System.out.println(returnSet); 
     return returnSet; 
    } 

    protected void incrementBitSet() { 
     for (int i = 0; i < bset.size(); i++) { 
      if (!bset.get(i)) { 
       bset.set(i); 
       break; 
      } else 
       bset.clear(i); 
     } 
    } 

    protected int countBitSet() { 
     int count = 0; 
     for (int i = 0; i < bset.size(); i++) { 
      if (bset.get(i)) { 
       count++; 
      } 
     } 
     return count; 

    } 

    protected String printBitSet() { 
     StringBuilder builder = new StringBuilder(); 
     for (int i = 0; i < bset.size(); i++) { 
      if (bset.get(i)) { 
       builder.append('1'); 
      } else { 
       builder.append('0'); 
      } 
     } 
     return builder.toString(); 
    } 

    @Override 
    public void remove() { 
     throw new UnsupportedOperationException("Not Supported!"); 
    } 

    @Override 
    public Iterator<Set<E>> iterator() { 
     return this; 
    } 

    public static void main(String[] args) { 
     Set<Character> set = new TreeSet<Character>(); 
     for (int i = 0; i < 7; i++) 
      set.add((char) (i + 'A')); 

     PowerSet<Character> pset = new PowerSet<Character>(set, 3, 5); 
     int count = 1; 
     for (Set<Character> s : pset) { 
      System.out.println(count++ + ": " + s); 
     } 
    } 

} 

這裏是測試結果：

1: [A, B, C] 
2: [A, B, D] 
3: [A, C, D] 
4: [B, C, D] 
5: [A, B, C, D] 
6: [A, B, E] 
7: [A, C, E] 
8: [B, C, E] 
9: [A, B, C, E] 
10: [A, D, E] 
11: [B, D, E] 
12: [A, B, D, E] 
13: [C, D, E] 
14: [A, C, D, E] 
15: [B, C, D, E] 
16: [A, B, C, D, E] 
17: [A, B, F] 
18: [A, C, F] 
19: [B, C, F] 
20: [A, B, C, F] 
21: [A, D, F] 
22: [B, D, F] 
23: [A, B, D, F] 
24: [C, D, F] 
25: [A, C, D, F] 
26: [B, C, D, F] 
27: [A, B, C, D, F] 
28: [A, E, F] 
29: [B, E, F] 
30: [A, B, E, F] 
31: [C, E, F] 
32: [A, C, E, F] 
33: [B, C, E, F] 
34: [A, B, C, E, F] 
35: [D, E, F] 
36: [A, D, E, F] 
37: [B, D, E, F] 
38: [A, B, D, E, F] 
39: [C, D, E, F] 
40: [A, C, D, E, F] 
41: [B, C, D, E, F] 
42: [A, B, G] 
43: [A, C, G] 
44: [B, C, G] 
45: [A, B, C, G] 
46: [A, D, G] 
47: [B, D, G] 
48: [A, B, D, G] 
49: [C, D, G] 
50: [A, C, D, G] 
51: [B, C, D, G] 
52: [A, B, C, D, G] 
53: [A, E, G] 
54: [B, E, G] 
55: [A, B, E, G] 
56: [C, E, G] 
57: [A, C, E, G] 
58: [B, C, E, G] 
59: [A, B, C, E, G] 
60: [D, E, G] 
61: [A, D, E, G] 
62: [B, D, E, G] 
63: [A, B, D, E, G] 
64: [C, D, E, G] 
65: [A, C, D, E, G] 
66: [B, C, D, E, G] 
67: [A, F, G] 
68: [B, F, G] 
69: [A, B, F, G] 
70: [C, F, G] 
71: [A, C, F, G] 
72: [B, C, F, G] 
73: [A, B, C, F, G] 
74: [D, F, G] 
75: [A, D, F, G] 
76: [B, D, F, G] 
77: [A, B, D, F, G] 
78: [C, D, F, G] 
79: [A, C, D, F, G] 
80: [B, C, D, F, G] 
81: [E, F, G] 
82: [A, E, F, G] 
83: [B, E, F, G] 
84: [A, B, E, F, G] 
85: [C, E, F, G] 
86: [A, C, E, F, G] 
87: [B, C, E, F, G] 
88: [D, E, F, G] 
89: [A, D, E, F, G] 
90: [B, D, E, F, G] 
91: [C, D, E, F, G] 

Answer 2

請指定元素的數量是否有界。

對於3 - 5,6元素來說，一組索引是可行的，可能是short[6]。

例如與高達32元件的int可容納設定，和一個既可以：

// dumb: 
for (int mask = 0; ; ;) { 
    int cardinality = Integer.bitCount(mask); 
    if (3 <= cardinality && cardinality <= 6) { 
     ... 
    } 
} 

在超過64個元素仍然也許位集合將提供緊湊性。

這裏的決定受到簡單統計的約束：有多少元素等等。 對於int/long/BitSet解決方案，可以從BitSet開始，因爲它有更好的API。例如，可以通過翻轉兩位來使用相同的位數來進入下一個powerset。如果一個人在數學上傾向於，De Bruijn週期可能會很有趣。

Answer 3

對於設置其大小不超過63元，如果你有一個最小尺寸的限制是不低的，這個實現可能會更快：

import java.util.Iterator; 
import java.util.LinkedList; 
import java.util.List; 
import java.util.Set; 

import static com.google.common.base.Preconditions.checkArgument; 
import static java.lang.Math.min; 

public class PowerSet<E> implements Iterator<Iterable<E>>, Iterable<Iterable<E>> { 

    private int minSize; 
    private int maxSize; 
    private E[] arr = null; 
    private long bits = 0; 
    private long count = 0; 
    private long minMask = 0; 

    /** 
    * Build a PowerSet of the given {@link Set} to iterate over subsets whose size is between the given boundaries 
    * @param set the set to create subsets from 
    * @param minSize the minimal size of the subsets 
    * @param maxSize the maximum size of the subsets 
    */ 
    @SuppressWarnings("unchecked") 
    public PowerSet(Set<E> set, int minSize, int maxSize) { 
     checkArgument(maxSize < 63); // limited to 63 because we need one additional bit for hasNext 
     this.minSize = min(minSize, set.size()); 
     this.maxSize = min(maxSize, set.size()); 
     arr = (E[]) set.toArray(); 
     for (int n = 0; n < minSize; n++) { 
      bits |= (1L << n); 
     } 
     count = countBitSet(bits); 
    } 

    @Override 
    public boolean hasNext() { 
     return (bits & (1L << arr.length)) == 0; 
    } 

    @Override 
    public Iterable<E> next() { 
     // compute current subset 
     final List<E> returnSet = new LinkedList<>(); 
     for (int i = 0; i < arr.length; i++) { 
      if ((bits & (1L << i)) != 0) { 
       returnSet.add(arr[i]); 
      } 
     } 

     // compute next bit map for next subset 
     do { 
      if (count < minSize) { 
       long maxFree = lowestIndex(bits) - 1; 
       long missing = minSize - count; 
       for (int n = 0; n < min(maxFree, missing); n++) { 
        bits |= (1L << n); 
       } 
      } else { 
       bits++; 
      } 
      count = countBitSet(bits); 
     } while ((count < minSize) || (count > maxSize)); 
     return returnSet; 
    } 

    /** 
    * Lowest set bit in a long word 
    * @param i the long word 
    * @return lowest bit set 
    */ 
    private static long lowestIndex(long i) { 
     int n = 0; 
     while (n < 64 && (i & 1L) == 0) { 
      n++; 
      i = i >>> 1; 
     } 
     return n; 
    } 

    /** 
    * Compute the number of bit sets inside a word or a long word.<br/> 
    * <a href="http://en.wikipedia.org/wiki/Hamming_weight">Hamming weight</a> 
    * @param i the long word 
    * @return number of set bits 
    */ 
    private static long countBitSet(long i) { 
     i = i - ((i >>> 1) & 0x5555555555555555L); 
     i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L); 
     i = ((i + (i >>> 4)) & 0x0F0F0F0F0F0F0F0FL); 
     return (i * (0x0101010101010101L)) >>> 56; 
    } 

    @Override 
    public void remove() { 
     throw new UnsupportedOperationException("Not Supported!"); 
    } 

    @Override 
    public Iterator<Iterable<E>> iterator() { 
     return this; 
    } 

} 

它由長而不是BitSet支持，並且計算下一個子集的速度更快...... 對於最小限制較低的情況，它可能也會更快。

可以刪除了番石榴的依賴是隻用於構造checkArgument ...