Project Euler Question 265

[Panphobia]

http://projecteuler.net/problem=265 for this project euler question, they are saying, "2N binary digits can be placed in a circle so that all the N-digit clockwise subsequences are distinct." I understand that the first N bits are 0 and the last digit is a 1 and that the N+1 digit is also a 1, what I am asking is how the problem for S(3) is 00011101 and 00010111 and not also 00011011, if this could be explained that would be great, i solved the question somehow, I do not even know how, I was pushing the bits and checking for duplications, I also dont understand they got those two answers for S(3) out of all these different combinations 000, 001, 010, 101, 011, 111, 110 and 100. am i missing something here? is it to create a binary number that when pushed bit by bit into the binary num of N digits each push gives a distinct value?

[Zren]

code:

00010111 000         0  001        1   010       2    101      5     011     3      111    7 0     11    6 00     1    4

Or at least that's what I think it means.

Edit: That totally wasn't the question.

[Panphobia]

Ok so basically I need to create all combinations of 2^N-N-2 bits and then add a 1 to the top and 1 to the bottom, after that i push it bit by bit into the binary number of length N, if there are duplicated when i push the values, i discard that combination, else i save it and move to the next one, so basically i can bruteforce this question pretty easily huh?

[Zren]

Panphobia @ Fri Dec 28, 2012 8:02 pm wrote:

all combinations of 2^N-N-2 bits

I get the -N bits (the first N bits are zero), but where does the -2 come in? Ah. That's right. You can't have a 0 substring bigger than N or you'll get a duplicate subsequence. Smart.

N=5 will make 25 boolean states, which makes 33554432 probabilities.

You could further refine your brute forcing by... Hmmm...

[Panphobia]

Well I created a method that gives permutations of strings so I create a new binary string of 2^5-5-2 with all 0s and add a 1 and remove a zero and get all permutations of that and I will keep adding 1's and removing zeros until they are all 1's and I'm getting the permutations all throughout this time, that should work right,

[Zren]

Um. What's the difference in what you described, and counting from 0 to 2^(2^5-5-2) then converting that number into binary?

The first permutation would be a bunch of zeroes (and thus, invalid). Have you considered how your going to validate these permutations?

[Panphobia]

I have a method that treats every digit differentley, I'll post it when I get on my desktop

[Panphobia]

Here is a method that gives you the permutations of a given string, it doesnt matter if it has the same digits, but i wouldnt give permutations for all 1's or all 0's because that is just a waste, but here

code:

static void permutation(String str, int length, String output, boolean[] used, int position) {         if (position == length) {             output = "000001" + output + "1";             total.add(output);             output = output.substring(6, output.length() - 1);             return;         } else {             for (int i = 0; i < length; i++) {                 if (used[i]) {                     continue;                 }                 output += str.charAt(i);                 used[i] = true;                 permutation(str, length, output, used, position + 1);                 output = output.substring(0, output.length() - 1);                 used[i] = false;             }         }     }

basically it locks the first digit in loops through collects the second digit and locks it in sets it as used, and then it does this until it completes one permutation then, it starts with the second digit and locks it in etc etc until all permutations are listed