Computer Science Canada

Project Euler Question 265
Author:  Panphobia [ Fri Dec 28, 2012 6:46 pm ]
Post subject:  Project Euler Question 265
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?
Author:  Zren [ Fri Dec 28, 2012 6:58 pm ]
Post subject:  RE:Project Euler Question 265
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.
Author:  Panphobia [ Fri Dec 28, 2012 7:02 pm ]
Post subject:  RE:Project Euler Question 265
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?
Author:  Zren [ Fri Dec 28, 2012 8:05 pm ]
Post subject:  Re: RE:Project Euler Question 265
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...
Author:  Panphobia [ Fri Dec 28, 2012 9:29 pm ]
Post subject:  RE:Project Euler Question 265
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,
Author:  Zren [ Fri Dec 28, 2012 11:43 pm ]
Post subject:  RE:Project Euler Question 265
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?
Author:  Panphobia [ Sat Dec 29, 2012 12:01 am ]
Post subject:  RE:Project Euler Question 265
I have a method that treats every digit differentley, I'll post it when I get on my desktop
Author:  Panphobia [ Sat Dec 29, 2012 12:24 am ]
Post subject:  Re: Project Euler Question 265
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

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy