Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Project Euler Question 265
Index -> General Programming
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Panphobia




PostPosted: 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?
Sponsor
Sponsor
Sponsor
sponsor
Zren




PostPosted: 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.
Panphobia




PostPosted: 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?
Zren




PostPosted: 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...
Panphobia




PostPosted: 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,
Zren




PostPosted: 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?
Panphobia




PostPosted: 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
Panphobia




PostPosted: 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
Sponsor
Sponsor
Sponsor
sponsor
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 8 Posts ]
Jump to:   


Style:  
Search: