获得n元组中的所有1-k元组

当n = 5且k = 3时，以下循环将执行此操作

List l=new ArrayList(); l.add("A");l.add("B");l.add("C");l.add("D");l.add("E"); int broadcastSize = (int) Math.pow(2, l.size()); for (int i = 1; i  0) { if ((mask & 1) == 1) { System.out.println(".. "+mask); buffer.append(l.get(j)); if (++size>3){ buffer = new StringBuffer(50); break; } } System.out.println(" "+mask); mask >>= 1; j++; } if (buffer.length()>0) System.out.println(buffer.toString()); } 

但是效率不高我想用银行家的序列去做，然后探索第一个单身，然后是对，然后是3元组和停止。

我没有找到办法，但至少这个循环应该更有效：

 List l=new ArrayList(); l.add("A");l.add("B");l.add("C");l.add("D");l.add("E"); int broadcastSize = (int) Math.pow(2, l.size()); for (int i = 1; i < broadcastSize; i++) { StringBuffer buffer = new StringBuffer(50); int mask = i; int j = 0; if (StringUtils.countMatches(Integer.toBinaryString(i), "1")  0) { if ((mask & 1) == 1) { buffer.append(l.get(j)); } mask >>= 1; j++; } if (buffer.length()>0) System.out.println(buffer.toString()); } } 

还有：但是k嵌入式循环看起来很难看

 //singleton for (int i = 0; i < l.size(); i++) { System.out.println(l.get(i)); } //pairs for (int i = 0; i < l.size(); i++) { for (int j = i+1; j < l.size(); j++) { System.out.println(l.get(i)+l.get(j)); } } //3-tuple for (int i = 0; i < l.size(); i++) { for (int j = i+1; j < l.size(); j++) { for (int k = j+1; k < l.size(); k++) { System.out.println(l.get(i)+l.get(j)+l.get(k)); } } } //... // k-tuple 

Answer 1

这种技术被称为Gosper的黑客 。 它仅适用于n <= 32因为它使用int的位，但如果使用long则可以将其增加到64。

 int nextCombo(int x) { // moves to the next combination with the same number of 1 bits int u = x & (-x); int v = u + x; return v + (((v ^ x) / u) >> 2); } ... for (int x = (1 << k) - 1; (x >>> n) == 0; x = nextCombo(x)) { System.out.println(Integer.toBinaryString(x)); } 

对于n = 5和k = 3 ，打印

 111 1011 1101 1110 10011 10101 10110 11001 11010 11100 

完全如你所料。

Answer 2

这应该是最有效的方式，即使k嵌入式循环看起来很难看

 //singleton for (int i = 0; i < l.size(); i++) { System.out.println(l.get(i)); } //pairs for (int i = 0; i < l.size(); i++) { for (int j = i+1; j < l.size(); j++) { System.out.println(l.get(i)+l.get(j)); } } //3-tuple for (int i = 0; i < l.size(); i++) { for (int j = i+1; j < l.size(); j++) { for (int k = j+1; k < l.size(); k++) { System.out.println(l.get(i)+l.get(j)+l.get(k)); } } } // ... //k-tuple 

Answer 3

Apache commons具有大小为k的子集和排列的迭代器。 这是一个迭代器，它迭代n-tuple的1-k元组，它结合了两个：

 import java.util.ArrayList; import java.util.Arrays; import java.util.Iterator; import java.util.List; import org.apache.commons.collections4.iterators.PermutationIterator; import org.apache.commons.math3.util.Combinations; public class AllTuplesUpToKIterator implements Iterator> { private Iterator combinationIterator; private PermutationIterator permutationIterator; int i; int k; int n; public AllTuplesUpToKIterator(int n, int k) { this.i = 1; this.k = k; this.n = n; combinationIterator = new Combinations(n, 1).iterator(); permutationIterator = new PermutationIterator(intArrayToIntegerList(combinationIterator.next())); } @Override public boolean hasNext() { if (permutationIterator.hasNext()) { return true; } else if (combinationIterator.hasNext()) { return true; } else if (i next() { if (!permutationIterator.hasNext()) { if (!combinationIterator.hasNext()) { i++; combinationIterator = new Combinations(n, i).iterator(); } permutationIterator = new PermutationIterator(intArrayToIntegerList(combinationIterator.next())); } return permutationIterator.next(); } @Override public void remove() { // TODO Auto-generated method stub } public static List intArrayToIntegerList(int[] arr) { List result = new ArrayList(); for (int i=0; i< arr.length; i++) { result.add(arr[i]); } return result; } public static void main(String[] args) { int n = 4; int k = 2; for (AllTuplesUpToKIterator iter= new AllTuplesUpToKIterator(n, k); iter.hasNext();) { System.out.println(iter.next()); } } }