 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / December 2005Please Help!!Daughter needs help with java code
Hello everyone, I apologize for taking up anyone's time with such a newbie question. However, my daughter is tearing her hair out over this code. I myself don't know anything about programming however, being the father that I am, I am hoping that someone can respond to my plea for help and provide her with a solution. Below is her code. Thank you all and God Bless!! Problem: Print out all the 4 number combinations using only the following numbers: 6, 9,0,3,1 The code is giving her only 5 combinations at the moment. This is where she needs help. //Source code// import java.math.BigInteger; public class NumGen { public static void main(String[] args) { char[] elements = {'6', '9', '0', '3', '1'}; int[] indices; CombinationGenerator x = new CombinationGenerator (elements.length, 4); StringBuffer combination; while (x.hasMore ()) { combination = new StringBuffer (); indices = x.getNext (); for (int i = 0; i < indices.length; i++) { combination.append (elements[indices[i]]); } System.out.println (combination.toString ()); } } } > Problem: Print out all the 4 number combinations using only the > following numbers: 6, 9,0,3,1 The problem statement is not clear to me. Is it asking for all strings of length 4 whose alphabet is {6, 9, 0, 3, 1}? Or is it asking to print all permutations of the set {6,9,0,3,1}, except don't print the last character? Or something else? Here's a legal string from the first interpretation which is not legal in the second interpretation, in case the difference isn't clear: 0000. - Oliver Thanks for the reply Oliver. Sorry for the confusion. She is trying to find all strings of length 4 whose alphabet is {6,9,0,3,1). In other words, find all the possible number combinations for {6,9,0,3,1) of lenght 4. Sorry if I am still not clear. I'm not a programmer. Thank you all for your help!! > Thanks for the reply Oliver. Sorry for the confusion. She is trying > to find all strings of length 4 whose alphabet is {6,9,0,3,1). In > other words, find all the possible number combinations for {6,9,0,3,1) > of lenght 4. Sorry if I am still not clear. I'm not a programmer. > > Thank you all for your help!! Does she know what recursion is? - Oliver > Thanks for the reply Oliver. Sorry for the confusion. She is trying > to find all strings of length 4 whose alphabet is {6,9,0,3,1). In > other words, find all the possible number combinations for {6,9,0,3,1) > of lenght 4. Sorry if I am still not clear. I'm not a programmer. The part that is unclear is whether this is sampling with replacement or sampling without replacement. In other words, is 9933 a possible solution or are we restricted to solutions such as 9613? BTW, how old are the kids getting this assignment? Were they given the CombinationGenerator code to work with? CombinationGenerator looks like a nice piece of code; I could of used it for the send-up that my 9 year old and I programmed to protest the difficulty of the Magic Square math homework given to my 6 year old. You also did not paste an additional class file CombinationGenerator. Also what's the purpose this class?? http://www.binaryfrost.com > You also did not paste an additional class file CombinationGenerator. > Also what's the purpose this class?? It's almost certainly this class (or something very similar) http://www.merriampark.com/comb.htm I stumbled across it myself a few weeks back when looking for some code to generate combinations. The algorithm is sound but I modified it to work with longs rather than BigIntegers since I didn't need to work with big sets and I used generics to get it actually generate the combinations as arrays of the appropriate type rather than just an int array of indices. Dan.  SignatureDaniel Dyer http://www.dandyer.co.uk Daniel, Thanks for the link, however, how would she modify the code to only do 9,6,3,0,1 instead of alphabets of length 4? > Thanks for the link, however, how would she modify the code to only do > 9,6,3,0,1 instead of alphabets of length 4? If this is an assignment, turning in someone else's code, even modified, is probably a bad idea. > http://www.merriampark.com/comb.htm > > I stumbled across it myself a few weeks back when looking for some code to > generate combinations. Nice algorithm. Does anyone know of something comparatively slick for generating permutations ? I like the way that the state of the overall iteration is implicit in the state of the array ('a' in the code on the website). It's straightforward to modify the idea so that it generates all combinations with repetitions included, and even more straightforward to make it generate all permutations with repetitions included, but I can't think of a comparably small change that would make it do "normal" permutations where repetitions are not included. It's pretty easy to generate permutations by recursion, but converting a deeply recursive algorithm into one suitable for external iteration would take, I think, a Stack of Iterators -- which seems excessive when the other three closely related algorithms can be handled so elegantly. BTW, in case it's not clear (I'm not sure if I'm using the standard terminology) to illustrate what I mean by permutations/combinations with/without repetitions. Given the source collection {A B C}, and wanting sub-collections of length 2, I mean Combinations: AB AC BA Permutations: AB AC BA BC CA CB Combinations with repetition: AA AB AC BB BC CC Permutations with repetition: AA AB AC BA BB BC CA CB CC -- chris > BTW, in case it's not clear (I'm not sure if I'm using the standard > terminology) to illustrate what I mean by permutations/combinations > with/without repetitions. Given the source collection {A B C}, and > wanting > sub-collections of length 2, I mean > Combinations: AB AC BA Did you mean "AB AC BC"? > Permutations: AB AC BA BC CA CB > Combinations with repetition: AA AB AC BB BC CC > Permutations with repetition: AA AB AC BA BB BC CA CB CC - Oliver > > Combinations: AB AC BA > > Did you mean "AB AC BC"? I do, yes. Thanks. -- chris On Fri, 2 Dec 2005 20:11:21 -0000, "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> wrote, quoted or indirectly quoted someone who said : >Nice algorithm. Does anyone know of something comparatively slick for >generating permutations ? see http://mindprod.com/jgloss/permutation.html SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. >> http://www.merriampark.com/comb.htm >> [quoted text clipped - 4 lines] > Nice algorithm. Does anyone know of something comparatively slick for > generating permutations ? Same site: http://www.merriampark.com/perm.htm Dan. SignatureDaniel Dyer http://www.dandyer.co.uk > http://www.merriampark.com/perm.htm The BigInteger code is a bit clunky. Some code that uses an array of integers instead of BigInteger to examine permutations in "magic chains" is at www.segal.org/java/FastChain9/. Output in the form of an array of integers is also more useful if you are treating the results as a bunch of digits to check whether the digits meet particular criteria, as in the magic chain applet. > http://www.merriampark.com/perm.htm Thanks to everyone who replied. The thing is that all of the solutions referred to seem to be based on exchanging elements. And that clearly cannot generate all the permutations of length 2 of elements of the string A B C. In fact I couldn't find anything that didn't start off by being dazzled by the mathematical purity of exchanging elements. The best references I found were a 1977 review paper by Sedgewick (which starts off by saying "Over thirty algorithms have been published during the last twenty years for generating [permutations]", and then unifies them into a framework based on exchanges), and -- inevitably -- Knuth. It's all very interesting, but none of it does what I want :-( It isn't that I don't know how to generate permutations (of substrings). For instance any of the above algorithms could be applied to each combination in turn. But it seems strange that while one can iterate over any of: the length R combinations, the length R combinations-with-repetition, the length R permutations-with-repetition, and the length R subsequences[*] of N elements using minor variations to the framework in the original algorithm, there is no obvious way of doing the permutations with the same framework. It is obvious that the auxiliary array 'a' /does/ contain enough information to permit generating permutations -- just iterate the permutations-with-repetition skipping candidates with repeated elements, but that's O(N**R) not O(N perm R). I still suspect that it /should/ be doable, but can't think of or find a way of doing it. (The nearest I've got so far requires keeping an addition Set of size O(R) and is basically the generate-and-discard algorithm with a bit of early pruning). -- chris ([*] same algorithm as for length R combinations) >The thing is that all of the solutions referred to seem to be >based on exchanging elements. And that clearly cannot generate >all the permutations of length 2 of elements of the string A B C. I am not sure whether "permutations" is the right term here, because a permutation AFAIK does not have a "length" specification. I have not read all the thread. If you really mean "permutations", it should be treated here: http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz >(...) the length R combinations, combinations: http://www-cs-faculty.stanford.edu/~knuth/fasc3a.ps.gz partitions: http://www-cs-faculty.stanford.edu/~knuth/fasc3a.ps.gz tuples: http://www-cs-faculty.stanford.edu/~knuth/fasc2a.ps.gz >The thing is that all of the solutions referred to seem to be >based on exchanging elements. And that clearly cannot generate >all the permutations of length 2 of elements of the string A B C. I am not sure whether "permutations" is the right term here, because a permutation AFAIK does not have a "length" specification. I have not read all the thread. If you really mean "permutations", it should be treated here: http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz >(...) the length R combinations, combinations: http://www-cs-faculty.stanford.edu/~knuth/fasc3a.ps.gz partitions: http://www-cs-faculty.stanford.edu/~knuth/fasc3b.ps.gz tuples: http://www-cs-faculty.stanford.edu/~knuth/fasc2a.ps.gz >http://www-cs-faculty.stanford.edu/~knuth/fasc2a.ps.gz For reference, all fascicles I am aware of: 0b Boolean Basics 1 MMIX 2a Generating all n-Tuples 2b Generating all Permutations 2c (now named "3a") 3a Generating all Combinations 3b Generating all Partitions 4a Generating all Trees 4b History of Combinatorial Generation > I am not sure whether "permutations" is the right term here, > because a permutation AFAIK does not have a "length" > specification. I agree. I did warn the reader that I might not be using the terms in a completely standard way (about 2 posts back), and attempt to explain what I meant. FWIW, by "permutation of length R" I mean the things that are counted by N perm R. > http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz ... and other links... Thank you. That looks fascinating. There's an immense amount to digest there, but I'm hopeful that if an answer to my question is known, then it'll be in there somewhere. (Provided I still remember what I'm looking for by the time I reach it ;-) /And/ I've learned a new word -- fascicle. 'Ain't life grand ? -- chris I wrote: > Thank you. That looks fascinating. There's an immense amount to digest > there, but I'm hopeful that if an answer to my question is known, then > it'll be in there somewhere. I don't suppose it's very likely that anyone except myself is even remotely interested in this, but FWIW.... It seems that Knuth's new stuff doesn't contain anything to help with this problem. I've been around and around it several times, and I've pretty much concluded that there is no way of generating R permutatons of N things in R space (not O(R) space, just an array of R integers) without introducing an extra O(R*R) looping factor. It can be done in R+R space in several apparently very different ways, so I'm becoming convinced that that is in fact a hard lower limit (though I can't prove it :-( -- chris >I wrote: > [quoted text clipped - 5 lines] > remotely > interested in this, but FWIW.... I'm interested, though I'm going through this much more slowly than you, it seems. I'm still idlely toying in my head with different algorithms for elegantly solving the four original problems you posed without any restriction on time or space yet. - Oliver What do you mean by "space?" Are you talking about the number of calculations, or the size of the data set you're looping in? It seems like there should be ways of doing this with binary digits and either iteration or bitwise shifts. > What do you mean by "space?" Are you talking about the number of > calculations, or the size of the data set you're looping in? I assume it's a reference to complexity theory in computer science. "Time" is how long it takes to perform a calculation, and "Space" is how much memory (e.g. RAM) you need to perform that calculation. You can occasionally save on RAM if you're willing to spend more time (e.g. compressing data you're not currently using and decompressing the data you need to work with). The Time complexity is almost always at least as big as the Space complexity, because the more scrap paper you use, the more time you have to spend reading all the scribbled notes you made. So if a problem is O(n^2) in Space, it almost certainly also is O(n^2) in Time, if not slower. http://en.wikipedia.org/wiki/Computational_complexity_theory - Oliver > "Space" is how much memory (e.g. RAM) If memory is your only consideration, then you only need N bits to calculate permutations for N objects... because an object is either a member of the permutation (1) or not (0). Bitwise AND's for each bit can tell you how many bits you have turned on for any given value, so you could start with the first permutation (i.e. 7, or 111b, for 3 members), then iterate continuously, only storing those combinations with the correct number of bits turned on. I think there's a faster way to do it by shifting the bits instead of iterating the value. >> "Space" is how much memory (e.g. RAM) > [quoted text clipped - 5 lines] > members), then iterate continuously, only storing those combinations > with the correct number of bits turned on. I believe that there are N! permutations of N objects, so at the very least, you need log2(N!) to express the solution. But this doesn't exactly solve original problem in a satisfying way: Your program could just output that the zeroth permutation is the permutation known as "0, and the next one is the one known as "1", and so on. Rather, the problem is, given an input which is a permutation, e.g. "A B C", return the next permutation in the sequence, e.g. "A C B". If there are N objects, then you need log2(N) bits to identify and differentiate between each object, and you need to specify N of those objects, so just writing down the solution takes N log2(N) bits of memory. Maybe you'll also only need N log2(N) bits for "temporary scratch work" too, but maybe you'll need more. - Oliver > I believe that there are N! permutations of N objects Sorry, I was thinking of combinations. There are N!/k!(N-k)! combinations of k objects taken from a set of N members. Each object of the subset of k objects represents a binary 1 in the superset of N objects, the remaining objects represent a binary 0. So if I need the combinations of 3 objects taken from a set of 8 ({A,B,C,D,E,F,G,H}), I can represent each of the superset objects as a bit, and the entire superset as a byte: ABCDEFGH 00000111 So, for example, 7 (111b) would represent the valid subset {F,G,H}, eight (1000b) would represent the invalid subset {E} ... eleven (1011b) would represent the valid subset {E, G, H} and so on via iteration. But by increasing the space to N*3, you could simply left-shift the bits around and XOR across the three bytes: ABCDEFGH 00000001 00000010 00000100 -------------- 00000111 = H, G, F Since this can preserve order if needed, it could be used for permutations as well as combinations. So combinations = N/8 bytes of space minimum Permutations = N*k/8 bytes of space minimum > Since this can preserve order if needed, it could be used for > permutations as well as combinations. Oops. this would result in duplicate combinations, so it could *only* be used for running the permutations. > Permutations = N*k/8 bytes of space minimum I presume by "minimum" you mean, "just to write down the solution", since you didn't seem to do any analysis of temporary scratch-work space. In the case where k = N (i.e. you want a permutation for ALL objects in the set) this becomes (N^2)/8, but I showed in a previous post how you could write down the solution in N*log2(N) bits, which is smaller than (N^2)/8 for large values of N. - Oliver >I think there's a faster way to do it by shifting the bits instead of >iterating the value. You can generate all the combinations with just an add per combination. You can't get faster than that. see http://mindprod.com/jgloss/combination.html SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. > see http://mindprod.com/jgloss/combination.html I think he's got a different definition for the word "combination" than the mathematic definition. >> see http://mindprod.com/jgloss/combination.html > > I think he's got a different definition for the word "combination" than > the mathematic definition. I believe Roedy is using the same definition that I have in mind for this thread. - Oliver Sorry for the confusion everyone. I am trying my best to be clear. She is trying to print out all the possible number combinations of length 4 using only the following numbers: 6,9,0,3, and 1. > Sorry for the confusion everyone. I am trying my best to be clear. > She is trying to print out all the possible number combinations of > length 4 using only the following numbers: 6,9,0,3, and 1. To me, there is no new information in this post with respect to your original one. Here's what I understand (and have understood since the first post): The strings are of length 4. Using characters other than 6, 9, 0, 3, 1 is not permitted. You want ALL such strings. Here's what's unclear (and was unclear since the first post): Can the characters repeat? E.g. is 0000 a legal string? Is the fact that the numbers not in any discernable order of some significance? I.e. why didn't you say "0,1,3,6,9"? Why is BigInteger getting involved for such small integers? What is CombinationGenerator? Or more importantly, where did it come from? You daughter? The teacher? Somewhere else? - Oliver I think she copied the code from the link that Daniel provided. Hopefully this will clarify it, - The strings are of length 4. - Number combinations are only permitted to use the following characters: 6,9,0,3,1 I can't answer the rest of your questions b/c I don't understand the terminology. I am not a programmer. Thanks!! > I think she copied the code from the link that Daniel provided. > Hopefully this will clarify it, [quoted text clipped - 4 lines] > I can't answer the rest of your questions b/c I don't understand the > terminology. I am not a programmer. This is not a matter of being a programmer. It's a matter of an ambiguous problem statement. Your daughter would need to ask her professor for clarification (after, of course, understanding the ambiguity herself). Signaturewww.designacourse.com The Easiest Way To Train Anyone... Anywhere. Chris Smith - Lead Software Developer/Technical Trainer MindIQ Corporation >>I think she copied the code from the link that Daniel provided. >>Hopefully this will clarify it, [quoted text clipped - 9 lines] > professor for clarification (after, of course, understanding the > ambiguity herself). It's not quite as ambiguous if you have a math background. Permutation and combination have distinct meanings. The former contains duplication, the latter only allows each element to be used once. > It's not quite as ambiguous if you have a math background. Permutation > and combination have distinct meanings. The former contains > duplication, the latter only allows each element to be used once. Permutation and combination do indeed have distinct meanings... which I would expect to be well-known not just among those with math "backgrounds". However, the definition of permutation has nothing to do with allowing duplications. I'm not sure where you got that particular tidbit of false information. Neither permutations nor combinations are generally defined to allow for duplication. Signaturewww.designacourse.com The Easiest Way To Train Anyone... Anywhere. Chris Smith - Lead Software Developer/Technical Trainer MindIQ Corporation On Fri, 02 Dec 2005 22:48:40 -0600, Alan Krueger <wgzkid502@sneakemail.com> wrote, quoted or indirectly quoted someone who said : >It's not quite as ambiguous if you have a math background. Permutation >and combination have distinct meanings. The former contains >duplication, the latter only allows each element to be used once. That's not correct. See http://mindprod.com/jgloss/permutation.html http://mindprod.com/combination.html The important thing about permutation is order of a fixed set. The important thing about combination is which elements are included, regardless of order. SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. > On Fri, 02 Dec 2005 22:48:40 -0600, Alan Krueger > <wgzkid502@sneakemail.com> wrote, quoted or indirectly quoted someone [quoted text clipped - 10 lines] > The important thing about combination is which elements are included, > regardless of order. - A permutation, also called an "arrangement number" or "order", is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. The number of permutations on a set n of elements is given by n!( n factorial http://mathworld.wolfram.com/Permutation.html - A Combination, the number of ways of picking unordered outcomes from possibilities. Also known as the binomial coefficient or choice number and read "n choose j," http://mathworld.wolfram.com/Combination.html SignatureThanks in Advance... IchBin, Pocono Lake, Pa, USA http://weconsultants.servebeer.com/JHackerAppManager __________________________________________________________________________ 'If there is one, Knowledge is the "Fountain of Youth"' -William E. Taylor, Regular Guy (1952-) > Here's what's unclear (and was unclear since the first post): > > Can the characters repeat? E.g. is 0000 a legal string? > Is the fact that the numbers not in any discernable order of some > significance? I.e. why didn't you say "0,1,3,6,9"? I think he means combinations in the mathematical sense (i.e. ordering is unimportant and elements cannot be repeated). > Why is BigInteger getting involved for such small integers? Because the code to generate combinations calculates factorials. The largest factorial that can be stored in a Java long is 20!, which means without BigInteger source sets larger than 20 elements could not be used. This of course is not a problem for the set he posted. However, if this is homework and the CombinationGenerator was not provided by the teacher/lecturer, then the use of BigInteger would be a give-away that this code was not written specifically for the problem at hand. > What is CombinationGenerator? Or more importantly, where did it come > from? You daughter? The teacher? Somewhere else? Almost certainly from the link I posted. The class name, method names and general approach are identical and both use BigInteger. Dan. SignatureDaniel Dyer http://www.dandyer.co.uk Thanks for clarifying it for me Daniel! > Hello everyone, > [quoted text clipped - 4 lines] > for help and provide her with a solution. Below is her code. Thank > you all and God Bless!! After reading all of this, the only thing that comes to mind is that if your daughter needs help, she should probably be asking these questions herself. Having a non-programmer trying to translate for a programming student is ... sub-optimal. Signaturemonique Ask smart questions, get good answers: http://www.catb.org/~esr/faqs/smart-questions.html Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2008 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.