The question is withdrawn.
Welcome to the Java Programming Forums
The professional, friendly Java community. 21,500 members and growing!
The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.
>> REGISTER NOW TO START POSTING
Members have full access to the forums. Advertisements are removed for registered users.
The question is withdrawn.
Last edited by javaplus; March 3rd, 2010 at 06:41 PM. Reason: out of scope of these forums.
The largest array you can allocate is 2^31 - 1, much smaller than 10e9.
What is it your algorithm is trying to do? It is possible that accomplishing such a task via brute strength simply isn't possible either recursively or iteratively.
javaplus (March 2nd, 2010)
Is what you want an iterative tree traversal algorithm? That isn't too hard to make iterative.
All you need to do is to design a state machine with the following transitions:
START:
- if there is a left child of the root, go to it and transition to DOWN_LEFT
- otherwise, if there is a right child of the root, go to it and transition to DOWN_RIGHT
- otherwise, print the root and return.
DOWN_LEFT:
- if there is a a left child, go left and stay in DOWN_LEFT
- otherwise, if there is a right child, go right and transition to DOWN_RIGHT
- otherwise, print the node, go to the parent, and transition to UP_RIGHT
UP_RIGHT:
- if there is a right child, go right and transition to DOWN_RIGHT
- otherwise, print the node, go to the parent, and stay in UP_RIGHT (or halt if in the root)
DOWN_RIGHT:
- if there is a left child, go left and transition to DOWN_LEFT
- otherwise, if there is a right child, go right and stay in DOWN_RIGHT
- otherwise, print the node, go to the parent, and transition to UP_LEFT
UP_LEFT:
- if this is the right child of some node, go to that node and stay in UP_LEFT
- if this is the left child of some node, go to that node and transition to UP_RIGHT
- if this is the root, print the root and halt
Say we have the tree with 1 in the root, 2 and 3 as 1's left and right children, and 4, 5, 6, and 7 as the left and right children of 2 and 3, respectively. I illustrate the machine starting from root (1). I represent each state as an ordered pair (node, state).
(1, START)
(2, DOWN_LEFT)
(4, DOWN_LEFT)
(2, UP_RIGHT) => print 4
(5, DOWN_RIGHT)
(2, UP_LEFT) => print 5
(1, UP_RIGHT) => print 2
(3, DOWN_RIGHT)
(6, DOWN_LEFT)
(3, UP_RIGHT) => print 6
(7, DOWN_RIGHT)
(3, UP_LEFT) => print 7
(1, UP_LEFT) => print 3
halt => print 1
If you prefer that the nodes be visitited in some similar order, you should be able to modify the algorithm to walk a bit differently. I think you will agree that, under this scheme, each node is visited a maximum of three times (precisely: each node is visited n+1 times, where n is the number of children of the node). So for a binary tree we are talking about O(3n) = O(n) running time, with O(1) storage...
Let me know what you think of my website:
http://www.auburn.edu/~carpept
Comments or suggestions are appreciated!
I'm really not sure I understand what you're asking for... why do these iterative solutions not work?
After looking at your code a little more carefully, I think I might have deciphered what you are trying to do.
You want to generate all d-bit binary numbers which are solutions. You could simply generate all d-bit binary numbers and check them, but that would be prohibitively expensive. Therefore, you use a property of solutions that you can tell when a partial solution has been obtained. You want to skip all strings which have as a prefix a string which is not a partial solution, thereby vastly reducing the number of checked d-bit values (indeed to exactly the number of d-bit solutions).
Ok. Here's some pseudocode that I think might be a start.
- Start off with p = 1, d = 0, and s = 0^n.
while p > 0 do
- if d = 2, let p := p - 1, d := x + 1 such that x is the (p - 1)th digit of s.
- otherwise, do all of the following:
- replace the pth digit of s with d.
- if the first p digits of s constitute a partial solution, and p < n, then let p := p + 1, d = 0.
- elseif the first p digits of s constitute a partial solution, and p = n, then s is a solution. now let d := d + 1.
- elseif the first p digits of s do not constitute a partial solution, let d := d + 1.
Let's try this with, say, n = 3. We start with p = 1 and d = 0, and s = 000.
d < 2, so we go to the else clause.
we therefore replace the 1st digit of s with 0, obtaining s = 000.
say for the sake of argument that the first digit of s = 000 does constitute a partial solution. we let p = 2 and d = 0.
the loop iteration is now over.
d < 2 so we go to the else clause.
we therefore replace the 2nd digit of s with 0, obtaining s = 000.
say for the sake of argument that the first two digits of s = 000 do constitute a partial solution. we let p = 3 and d = 0.
the loop iteration is now over.
d < 2 so we go to the else clause.
we therefore replace the 3rd digit of s with 0, obtaining s = 000.
say for the sake of argument that the first three digits of s = 000 do constitute a partial solution. then 000 is a solution. we let d = 1.
the loop iteration is now over.
d < 2 so we go to the else clause.
we therefore replace the 3rd digit of s with 0, obtaining s = 001.
say for the sake of argument that the first three digits of s = 001 do not constitute a solution. then 001 is not a solution. we let d = 2.
the loop iteration is now over.
d = 2 so we let p = 2 and d = 1 (because x = 0, the 2nd digit of s, and d = x + 1).
the loop iteration is now over.
d < 2 so we go to the else clause.
we replace the 2nd digit of s with 1 to get s = 011.
say for the sake of argument that the first two digits of s = 011 do not constitute a partial solution. then let p = 2 and d = 2.
the loop iteration is now over.
d = 2, so we let p = 1 and d = 1.
the loop iteration is now over.
etc.
You probably see how it works. Is this what you're after? Notice that you really don't need a counter, per se, since the binary representations themselves should be enough to give you the decimal representation. Let me know if this is closer to what you were looking for. The translation to Java should be straightforward, but let me know if you want some proper pseudocode to look at.
Let me know what you think of my website:
http://www.auburn.edu/~carpept
Comments or suggestions are appreciated!
Just out of curiosity, does my algorithm do what you want? I'm still not sure I've even understood what you're trying to do.
And correct me if I'm wrong, but how does your start() function know where the end of the sequence is? Won't it just overshoot it as you have currently implemented it? You don't use 'n' anywhere inside it.
Also, if you want to talk about efficiency, my algorithm does it with O(1) storage. Not that yours is inefficient in this respect, just saying.
Just so you can test it out without too much work, here's a Java implementation:
void start() { int p = 0; byte d = 0; for(int i = 0; i < n; i++) sequence[i] = 0; while(p > -1) { if(d == 2) { p = p - 1; if(p > -1) d = sequence[p] + 1; } else { sequence[p] = d; if(!isPartialSolution(p)) { // have no solution or partial solution d = d + 1; } else if(p = n) { // p = n, have a complete solution printSequence(); d = d + 1; } else { // p < n, have a partial solution p = p + 1; d = 0; } } } }
I think that should be a faithful implementation. Also, yours should be fixable to account for the array length if that is a problem. Just something to think about...
Also, you might be clearer in the future when you are asking for help. There is no actual binary tree involved here, at best, just a hypothetical binary tree that you can think of as containing as paths strings of binary digits of length n. This is more easily couched in terms of strings (or arrays if you like), and both of our algorithms work this way.
How selective is your isPartialSolution() function? It had better be pretty selective if you want this scheme to work for any reasonable n.
Last edited by CT&SC; March 3rd, 2010 at 09:52 AM.
Let me know what you think of my website:
http://www.auburn.edu/~carpept
Comments or suggestions are appreciated!
"The code that I posted above is correct and there is no need to include n in the loop. You are welcome to run it and see for yourself that it stops."
- I think I now understand that you avoided checking the length in your algorithm by changing the definition of "partial solution" to mean strictly partial, as in, not complete. I hadn't realized you had redefined what it meant for a sequence to be a partial solution. Personally, I feel that this is sort of a kludge in the sense that you're redefining the natural problem definition (or at least what I very meagerly understood to be the problem) to suit implementation. Dirty, but I'll allow it.
"Your program produces array of integers."
I don't quite understand your objection to my algorithm's producing arrays of integers. An array of integers where all integers are either 0 or 1 is in fact a representation of a sequence of binary digits. The array [0, 1, 0, 0, 1] can easily be interpreted as the binary string 01001 and using any method of converting bases translated to 9 in base 10. So long as printSequence() is called every time the array contains a representation of a binary string which is a partial solution, I don't see a problem. As I demonstrated by hand previously, my algorithm seems like it is doing the right thing for the case n=3 and for a certain hypothetical isPartialSolution() function. Is that algorithm not doing the right thing?
I suppose I was sloppy when I said my algorithm is O(1). Technically, since it uses the global variable sequence[], it is O(n) where n is the number of things in sequence. The convention on this is normally to ignore global, static-size structures in algorithmic analysis, but since this structure just happens to be the same size as the problem size, that's probably not fair. In that sense, my algorithm is an O(n) storage algorithm. However, what I meant to say is that your state array is not necessary... it is redundant.
"There must be some state information to backtrack to!"
- Yes, here it is the sequence. The state array is not required.
I don't have access at the moment to a compiler, but I still tend to think the algorithm is correct, whatever the results of the proposed implementation are. I would appreciate it if you were to take a look at my post #6 to tell me at what stage the algorithm does something wrong.
Last edited by CT&SC; March 3rd, 2010 at 01:43 PM.
Let me know what you think of my website:
http://www.auburn.edu/~carpept
Comments or suggestions are appreciated!
Huh. Just implemented my version using javascript. I let n = 3 and made isPartialSolution the "true" function. Here's the output:
000
001
010
011
100
101
110
111
Is this not what you wanted? Let me now change isPartialSolution to return true except for strings starting with 10:
000
001
010
011
110
111
I'm really sorry, I'm convinced my algorithm works. There were a few problems with my implementation, but they were really easy to fix... just standard problems when one takes 1-indexed pseudocode and transforms it to an actual programming language. If you want me to try out any further examples, more complicated ones for larger n, say, let me know. I can also give you the cheap .html file with the implementation if you want it.
And I'll take your word for it that your implementation works... I believe after restructuring your code to better adhere to structured programming style our code would look more similar (I make reference to the while(true) and break combo). This was actually a pretty interesting (if trivial) problem... thanks for posting it. I'm sure a lot of people who just read this forum will learn a lot from the discussion...
Let me know what you think of my website:
http://www.auburn.edu/~carpept
Comments or suggestions are appreciated!
^ Just a clarification, my algorithm is already posted above and works (I'll leave as an exercise to the reader what needs to be changed about the java implementation to make it work).
Let me know what you think of my website:
http://www.auburn.edu/~carpept
Comments or suggestions are appreciated!