Please Help!!Daughter needs help with java code

[Alan Krueger]

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.

 

[Alan Krueger]

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).

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.

 

[Chris Smith]

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.

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Roedy Green]

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.

 

[IchBin]

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.

- 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

--


Thanks 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-)

 

[Chris Uppal]

Did you mean "AB AC BC"?

I do, yes. Thanks.

-- chris

 

[Mickey Segal]

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.

 

[Chris Uppal]

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)

 

[Stefan Ram]

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

 

[Stefan Ram]

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

 

[Stefan Ram]

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

 

[Chris Uppal]

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

 

[Chris Uppal]

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

 

[Oliver Wong]

I don't suppose it's very likely that anyone except myself is even
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

 

[slippymississippi]

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.

 

[Oliver Wong]

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

 

[slippymississippi]

"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.

 

[Oliver Wong]

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 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

 

[Roedy Green]

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

 

[slippymississippi]

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