I am trying to get all the unique bit combinations (really interesting ... I know..zzz). This basically works well for small numbers like 10 bits with 3 unique or 100 bits and 4 unique. I test it on a scale, but something strange happens when I use 200 bits and 30 elements. I get nothing. I tried to debug the code and can't figure out why.
I use all longs, so I'm not sure why, is the bit somehow limited or is it a problem with my math? Also, is this what I am making possible for a very large number of bits or is there some kind of limit (i.e., Burning out the sun before my program is executed)? Ideally, I would like to get 30 unique bits from the 2000 list. This approach was the only one that exceeds 100, but I do not know its limit.
Here is the code:
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
public class Combinatorics {
static final class CombinationsIterator implements Iterator<Long> {
private int n;
private int k;
private long next;
public CombinationsIterator(int n, int k) {
this.n = n;
this.k = k;
next = (1L << k) - 1;
}
@Override
public boolean hasNext() {
return (next & (1L << n)) == 0;
}
@Override
public Long next() {
long result = next;
long x = next;
long u = x & -x;
long v = u + x;
x = v + (((v ^ x) / u) >> 2);
next = x;
return result;
}
@Override
public void remove() { throw new UnsupportedOperationException(); }
}
static final class PermutationsIterator implements Iterator<List<Integer>> {
int n;
int k;
int nPk;
List<Integer> elements;
int i;
List<Integer> next;
public PermutationsIterator(int n, int k) {
this.n = n;
this.k = k;
nPk = permute(n, k);
List<Integer> elements = new ArrayList<Integer>();
for (int i = 0; i < n; i++)
elements.add(i);
this.elements = Collections.unmodifiableList(elements);
}
@Override
public boolean hasNext() { return i < nPk; }
@Override
public List<Integer> next() {
List<Integer> next = new ArrayList<Integer>();
List<Integer> notNext = new ArrayList<Integer>(elements);
int r = i;
int np = nPk;
for (int j = 0; j < k; j++) {
np /= n - j;
next.add(notNext.remove(r / np));
r %= np;
}
i++;
return next;
}
@Override
public void remove() { throw new UnsupportedOperationException(); }
}
public static long toCombination(List<Integer> permutation) {
long combination = 0;
for (int i : permutation)
combination |= (1L << i);
return combination;
}
public static List<Integer> toPermutation(long combination) {
List<Integer> permutation = new ArrayList<Integer>();
long combinationRemaining = combination;
int i = 0;
while (combinationRemaining > 0) {
if ((combinationRemaining & 1) > 0) {
permutation.add(i);
}
combinationRemaining >>= 1;
i++;
}
return permutation;
}
public static SortedMap<Integer, Integer> multiplicitiesOf(List<Integer> multiset) {
SortedMap<Integer, Integer> multiplicities = new TreeMap<Integer, Integer>();
for (Integer k : multiset) {
Integer v = multiplicities.get(k);
v = (v == null) ? 1 : (v + 1);
multiplicities.put(k, v);
}
return multiplicities;
}
public static Iterator<Long> combinationsIterator(int n, int k) {
return new CombinationsIterator(n, k);
}
public static Iterator<List<Integer>> permutationsIterator(int n, int k) {
return new PermutationsIterator(n, k);
}
public static int factorial(int n) {
int result = 1;
for (int i = 1; i <= n; i++)
result *= i;
return result;
}
public static int permute(int n, int k) {
int result = 1;
for (int i = n - k + 1; i <= n; i++)
result *= i;
return result;
}
public static int choose(int n, int k) {
return permute(n, k) / factorial(k);
}
public static void main(String[] args) throws IOException {
System.out.println("Starting");
for (Iterator<Long> it = combinationsIterator(200, 2); it.hasNext(); ) {
long next = it.next();
System.out.format("%d\t%10s\n", next, Long.toBinaryString(next));
}
}
}
In the method, the mainchange combinationsIterator(200, 2);creates strange behavior (10.3 gives the correct result very quickly, even 100.5 ... but as the number gets higher, it just does not give results, unlike the time for processing)
source
share