Получить все 1-к кортежи в виде п-кортежа

Question

С п = 5 и к = 3 следующий цикл будет делать это

List<String> l=new ArrayList<String>(); 
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; 
    int size=0; 
    System.out.println(); 
    while (mask > 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()); 

} 

но это не эффективно, я хотел бы сделать это с Banker's sequence и, таким образом, исследовать первые синглтоны, затем пары, затем 3-кортеж и остановка.

я не нашел способ сделать это, но, по крайней мере, этот цикл должен быть более эффективным:

List<String> l=new ArrayList<String>(); 
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") < 4){ 
     while (mask > 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

это должно быть наиболее эффективный способ, даже если 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 2

Этот метод называется Gosper's hack. Он работает только для n <= 32, потому что он использует бит int, но вы можете увеличить его до 64, если используете long.

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 3

Apache имеет итераторы для subsets размера k, а также для permutations. Вот итератор, который перебирает 1-К кортежам п-кортеж, который сочетает в себе два:

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<List<Integer>> { 
    private Iterator<int[]> combinationIterator; 
    private PermutationIterator<Integer> 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<Integer>(intArrayToIntegerList(combinationIterator.next())); 
    } 

    @Override 
    public boolean hasNext() { 
     if (permutationIterator.hasNext()) { 
      return true; 
     } else if (combinationIterator.hasNext()) { 
      return true; 
     } else if (i<k) { 
      return true; 
     } else { 
      return false; 
     } 
    } 

    @Override 
    public List<Integer> next() { 
     if (!permutationIterator.hasNext()) { 
      if (!combinationIterator.hasNext()) { 
       i++; 
       combinationIterator = new Combinations(n, i).iterator(); 
      } 
      permutationIterator = new PermutationIterator<Integer>(intArrayToIntegerList(combinationIterator.next()));   
     } 
     return permutationIterator.next(); 
    } 

    @Override 
    public void remove() { 
     // TODO Auto-generated method stub 

    } 

    public static List<Integer> intArrayToIntegerList(int[] arr) { 
     List<Integer> result = new ArrayList<Integer>(); 
     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()); 
     } 

    } 
}