$S$ is a symmetric set

  • If $|S|=3$ such that $S=\{n_1, n_2, n_3\}$ then $n_1+n_2 = n_3$,
  • If $|S|=4$ such that $S=\{n_1, n_2, n_3, n_4\}$ then $n_1+n_3=n_4$ and $2n_2=n_4$,
  • If $|S|=5$ such that $S=\{n_1, n_2, n_3, n_4, n_5\}$ then $n_1+n_4=n_2+n_3=n_5$.

Given a symmetric set $S$ and a string $a={a_0 \dots a_{n-1}}, \ \ \ a_i \in \{0,1\} \ \forall i \in \mathbb{N}$ with the length of $\max(S)$ (i.e., if $S=\{2,3,5\}$ then the length of $a$ is $5$ such that $a=a_0a_1a_2a_3a_4$), $a$ is zero-collision-free if $a_i + a_{i+n_j} \neq 0$ $\ \ \ \ \forall i$ and $j\in\{1,\dots,|S| \}$.

Example 1 : $S=\{1,5,6\}$, i.e., $n_1=1, \ n_2=5, \ n_3=6$

$a=110011$ is not zero-collision-free because $a_2 + a_{2+n_1}=a_2+a_3=0$.

$a=010101$ is zero-collision-free.

$a=010110$ is not zero-collision-free because $a_0 + a_{0+n_3}=a_0+a_5=0$.

Example 2 : $S=\{1,2,5,6,7\}$, i.e., $n_1=1, \ n_2=2, \ n_3=5, \ n_4=6, \ n_5=7$

$a=1110101$ is not zero-collision-free because $a_3 + a_{3+n_2}=a_3+a_5=0$.

$a=1110111$ is zero-collision-free.

$a=1011110$ is not zero-collision-free because $a_1 + a_{1+n_3}=a_1+a_6=0$.

My question :

Given a symmetric $S$ how can I create all zero-collision-free strings according to $S$ ? Okay, I have a solution(coded in Java) and it works, but it is very slow. I simply create every string having the length of $n$, namely $2^n$ strings, one by one then check each of them if they are zero-collision-free or not.

private List<StringBuilder> generateZeroCollisionFreeStrings(List<Integer> symmetricSet) {
    List<StringBuilder> zeroColFreeStrings = new ArrayList<>();
    int amountOfTuples = Collections.max(symmetricSet);  

    long time1 = System.nanoTime();

    allStrings: 
    for (int i = 0; i < (int) Math.pow(2, amountOfTuples); i++) {
        StringBuilder binaryString = new StringBuilder(
                String.format("%" + String.valueOf(amountOfTuples) + "s", Integer.toBinaryString(i))
                        .replace(' ', '0'));
        for (int j = 0; j < binaryString.length(); j++) {
            for (int k = 0; k < symmetricSet.size(); k++) {
                if (j + symmetricSet.get(k) < binaryString.length()) {
                    if (Integer.parseInt(binaryString.substring(j, j + 1)) + Integer.parseInt(binaryString
                            .substring(j + symmetricSet.get(k), j + symmetricSet.get(k) + 1)) == 0) {
                        continue allStrings;
                    } 
                }
            }
        }
        zeroColFreeStrings.add(binaryString);
    } 
    long time2 = System.nanoTime();
    System.out.println(time2 + " - " + time1  + " = " + (time2 - time1)/1000000000);

    return zeroColFreeStrings;
}

I need a better algorithm. If you have a better idea I would love to hear that. Thank you for any help you can provide.

  • An obvious improvement to this brute-force would be building strings character by character. What I mean is that in your first with S={1,5,6} any string that starts with 1100... is bound to fail no matter what the rest of the symbols is. P.S. is it true that in $a_i + a_{i+n_j} \neq 0$ the + is the usual arithmetic plus rather than more typical in such contexts "modulo 2 plus"? I mean 1+1 is 0 or 2? – SergGr Dec 5 at 0:21
  • @SergGr It is the usual addition not "modulo 2 plus". – water Dec 5 at 9:07
  • @SergGr Thank you for your answer. How can I build them character by character? Do you have an algorithm in your mind? – water Dec 5 at 14:49
up vote 0 down vote accepted

Since your code uses int as type for bit-strings I assume that max(S) is no more than 31 to fit. Here is some helper method to convert int into a 0-padded binary string:

static final int MAX_PAD = 32;
static final String[] PADS_0;

static {
    PADS_0 = new String[MAX_PAD + 1];
    String pad = "";
    for (int i = 0; i <= MAX_PAD; i++) {
        PADS_0[i] = pad;
        pad = pad + "0";
    }
}

static String intToPaddedBinaryString(int value, int stringLen) {
    String binaryString = Integer.toBinaryString(value);
    if (binaryString.length() < stringLen)
        binaryString = PADS_0[stringLen - binaryString.length()] + binaryString;
    return binaryString;
}

Just stop doing bad things

Even your original code can be done an order of magnitude faster by just avoiding doing things in a very inefficient way:

private static List<String> generateZeroCollisionFreeStrings1(List<Integer> symmetricSet) {
    List<String> zeroColFreeStrings = new ArrayList<>();
    int stringLen = Collections.max(symmetricSet);

    long time1 = System.nanoTime();

    allStrings:
    for (int i = 0; i < (int) Math.pow(2, stringLen); i++) {
        for (int j = 0; j < stringLen; j++) {
            int maskJ = i & (1 << j);
            if (maskJ == 0) {
                for (int k : symmetricSet) {
                    int kj = j + k;
                    if (kj < stringLen) {
                        int maskKJ = i & (1 << kj);
                        if (maskKJ == 0)
                            continue allStrings;
                    }
                }
            }
        }
        zeroColFreeStrings.add(intToPaddedBinaryString(i, stringLen));
    }
    long time2 = System.nanoTime();


    //System.out.println(zeroColFreeStrings.size());
    //System.out.println(Arrays.toString(zeroColFreeStrings.toArray()));
    System.out.println("Simple optimization: " + time2 + " - " + time1 + " = " + (time2 - time1) / 1_000_000);

    return zeroColFreeStrings;
}

Main differences are:

  1. Use bit-masks to check for 0 at given position instead of parsing it back from a string

  2. Optimization #1 allows converting the value to string only if it a 0-collision-free

  3. Do early exit. Particularly if Integer.parseInt(binaryString.substring(j, j + 1)) is 1 in other words if bit at the position j is 1, all check will pass. We need to check only if that bit is 0. And this is what check for maskJ == 0 does. Also inside we know that it is 0 so we can check only maskKJ

Those optimizations alone on my test data speed up the logic in the 5-100x range. Yes just those optimization are enough to get almost 100x speedup on some bigger test data.

Smarter algorithm

Still we can do better with a better algorithm. The idea is that if any binary string s is a zero-collision free and it has 0 at position pos, then the string s' with 1 at that position is obviously also 0-collision-free. It means that we can generate all such strings by adding 0s at some positions in the initial 11...11. And it is obvious that if we added some 0 and the new string is not a 0-collision-free, we can't fix it by adding more 0. So we can start with the leftmost bit and expand our initial string into two string 11...11 and 01...11, then go to the next bit position and try to add 0 to each available candidate from the previous step checking if the 0-collision-free still holds. Here is some code:

private static List<String> generateZeroCollisionFreeStringsSmarter(List<Integer> symmetricSet) {
    final long time1 = System.nanoTime();
    List<Integer> zeroColFreeBitStrings = new ArrayList<>();

    final int stringLen = Collections.max(symmetricSet);

    int all1 = (1 << stringLen) - 1;
    zeroColFreeBitStrings.add(all1);

    for (int bitPos = 0; bitPos < stringLen; bitPos++) {
        // fix the size as we will be adding back to the same list
        final int origSize = zeroColFreeBitStrings.size();
        checkBitString:
        for (int i = 0; i < origSize; i++) {
            int bits = zeroColFreeBitStrings.get(i);
            // check if we can clear bit at pitPos
            for (int dif : symmetricSet) {
                if (dif <= bitPos) {
                    int maskDif = bits & (1 << (bitPos - dif));
                    if (maskDif == 0)
                        continue checkBitString;
                }
            }

            // create bits with 0 at bitPos
            int newBits = bits & ~(1 << bitPos);
            zeroColFreeBitStrings.add(newBits);
        }
    }

    zeroColFreeBitStrings.sort(Integer::compareTo);
    List<String> zeroColFreeStrings = zeroColFreeBitStrings.stream()
            .map(bits -> intToPaddedBinaryString(bits, stringLen))
            .collect(Collectors.toList());

    long time2 = System.nanoTime();
    //System.out.println(zeroColFreeStrings.size());
    //System.out.println(Arrays.toString(zeroColFreeStrings.toArray()));
    System.out.println("Smarter algo " + time2 + " - " + time1 + " = " + (time2 - time1) / 1_000_000);


    return zeroColFreeStrings;
}

This code on my test data adds another 5-15x speed up.

  • Hey! This is not a programming site. – Yuval Filmus Dec 6 at 3:44
  • @YuvalFilmus, I know but I'm not sure what else I can do when the programming-related things account for 100x of speedup and a better algorithm just for 10x. – SergGr Dec 6 at 3:47
  • Suggest migrating the question to a more appropriate site. – Yuval Filmus Dec 6 at 3:48
  • @YuvalFilmus, I see no obvious mechanism for that on this site. Maybe just not enough points. Feel free to do it yourself. – SergGr Dec 6 at 3:54
  • @SergGr Thank you very much for the great comprehensive answer. – water Dec 7 at 15:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.