> How many different ways are there to arrainge 16
> things?
> I know it's simple, but I can't think of it offhand.
>
> --
> Feel the power of the dark side! Atmel AVR
> --
On 4/6/06, kravnus wolf <.....kravnusKILLspam@spam@yahoo.com> wrote:
>
> 16*15*14*13*......*1
>
> john
>
> --- David VanHorn <dvanhornKILLspammicrobrix.com> wrote:
>
> > How many different ways are there to arrainge 16
> > things?
> > I know it's simple, but I can't think of it offhand.
> >
> > --
> > Feel the power of the dark side! Atmel AVR
> > --
> On 4/6/06, kravnus wolf <EraseMEkravnusspam_OUTTakeThisOuTyahoo.com> wrote:
>
>>16*15*14*13*......*1
>
>
>
> I thought about that, but the number seemed too large somehow.
> Thanks!
>
> --
>
>>Feel the power of the dark side! Atmel AVR
> On 4/6/06, kravnus wolf <@spam@kravnusKILLspamyahoo.com> wrote:
> >
> > 16*15*14*13*......*1
>
>
> I thought about that, but the number seemed too
> large somehow.
> Thanks!
>
> --
> > Feel the power of the dark side! Atmel AVR
David VanHorn wrote:
> How many different ways are there to arrainge 16 things?
Many.
This is a bad question. Do you mean you have 16 different things and 16
discrete places to put these thing, how many different combinations are
there? That at least would be an answerable question.
Imagine what you would do to actually go thru all possible combinations.
You grab the first thing, which you can put in 16 different places. The
next thing can only go in 15 places, then next in 14, etc. Since this
operation comes up a lot, especially in statistics, it is given the special
name "factorial", usually written with "!". So the answer to your problem
is:
16 factorial = 16! = about 2.09e13
Like I said, many.
******************************************************************
Embed Inc, Littleton Massachusetts, (978) 742-9014. #1 PIC
consultant in 2004 program year. http://www.embedinc.com/products
If the number seems too large, perhaps it is. Keep in mind that if
any of the 16 items are the same then it will be smaller. For
instance, your 16 things could consist of
5 pennies
4 nickels
1 dime
6 quarters
In which case there are significantly fewer unique ways of ordering
them than if they were each different.
These kinds of problems are generally taught in upper level statistics
classes at universities, so you can probably go to your local library
and peruse the statistics books if you need to go into this further
than you already have.
On 4/6/06, David VanHorn <KILLspamdvanhornKILLspammicrobrix.com> wrote:
> On 4/6/06, kravnus wolf <RemoveMEkravnusTakeThisOuTyahoo.com> wrote:
> >
> > 16*15*14*13*......*1
>
>
> I thought about that, but the number seemed too large somehow.
> Thanks!
>
> --
> > Feel the power of the dark side! Atmel AVR
> -
> If the number seems too large, perhaps it is.
>(snip)
> These kinds of problems are generally taught in upper level statistics
> classes at universities,
No kidding? For me this was part of the exam of the school that preceded
university (VWO in my country, corresponds to your highschool?). I
*loved* this subject.
Wouter van Ooijen
-- -------------------------------------------
Van Ooijen Technische Informatica: http://www.voti.nl
consultancy, development, PICmicro products
docent Hogeschool van Utrecht: http://www.voti.nl/hvu
Wouter van Ooijen wrote:
> No kidding? For me this was part of the exam of the school that preceded
> university (VWO in my country, corresponds to your highschool?). I
> *loved* this subject.
Yeah, I remember that we did pretty much this same problem (with fewer
items) in 7th or 8th grade. This is really basic math.
******************************************************************
Embed Inc, Littleton Massachusetts, (978) 742-9014. #1 PIC
consultant in 2004 program year. http://www.embedinc.com/products
I was implementing an enigma machine in software.
In my simple version, I'm working on nybbles, so there are 16 positions on
my four "rotors"
So the question was actually like drawing cards or lottery numbers, in this
case, plugging wires into holes. Imagine that you have two halves of a
rotor wheel, with 16 wires in the left one, and 16 positions in the right.
You plug the first wire somewhere at random, and then the next wire has 15
possible locations, and so on, till the last one has to go in the last hole.
Each machine of course needs a set of identically built rotors, to decrypt
something that the other machine sent.
It's a fun exercise. I didn't implement the plugboard or rotation of the
letter positions on the rotors, but those are relatively uninteresting.
Mine increments the rotors odometer style, but you could easily do the
rotors in ways that would be pretty nasty in hardware, like a(1), b(3),
c(0), d(11) per "click".
Generating the rotor data automatically would be interesting, each rotor is
a 16 element table that needs to have no "repeats" Doing this in a provably
random way is not trivial, but for messing around you can just do it by
hand.
I got about 8mS to encrypt 32 bytes at 4 MHz, and used reverse lookups so
that I didn't need to generate forward and reverse tables for the rotors.
I might take this further and do it up with serial interface so it can be
played with outside of simulation.
I'm sorry Olin, that I didn't properly prepare my problem for publication in
"Nature". It was late, I was tired, and what I was asking was relatively
simple, and obviously many understood what I needed.
At 06:00 AM 4/6/2006, Olin Lathrop wrote:
>David VanHorn wrote:
> > How many different ways are there to arrainge 16 things?
>
>Imagine what you would do to actually go thru all possible combinations.
>You grab the first thing, which you can put in 16 different places. The
>next thing can only go in 15 places, then next in 14, etc. Since this
>operation comes up a lot, especially in statistics, it is given the special
>name "factorial", usually written with "!". So the answer to your problem
>is:
>
> 16 factorial = 16! = about 2.09e13
One of the best explanations I've ever seen. You'd probably make a
great teacher, Olin.
Celebrating 22 years of Engineering Innovation (1984 - 2006)
.-. .-. .-. .-. .-. .-. .-. .-. .-. .-
`-' `-' `-' `-' `-' `-' `-' `-' `-'
Do NOT send unsolicited commercial email to this email address.
This message neither grants consent to receive unsolicited
commercial email nor is intended to solicit commercial email.
> These kinds of problems are generally taught in upper level statistics
> classes at universities, so you can probably go to your local library
> and peruse the statistics books if you need to go into this further
> than you already have.
It's pretty amazing how non-intuitive probability can be. When
I was in "Mathletes" (competition Math club in HS), the probability
problems were always the ones that resulted in the most discussion.
I guess this helps explain gambling problems as well...
William Chops Westfield wrote:
> It's pretty amazing how non-intuitive probability can be. When
> I was in "Mathletes" (competition Math club in HS), the probability
> problems were always the ones that resulted in the most discussion.
> I guess this helps explain gambling problems as well...
That's why our state lottery is sometimes referred to as a tax on people
that are bad at math, or a "stupidity tax". Seems to work pretty well. I
always get a chuckle out of people mentioning that so-and-so won some money
in the lottery. Please, tell everyone, it will only encourage more to play.
I love it when other people pay my taxes for me.
******************************************************************
Embed Inc, Littleton Massachusetts, (978) 742-9014. #1 PIC
consultant in 2004 program year. http://www.embedinc.com/products
> It's pretty amazing how non-intuitive probability can be.
I've always found probability (and combinatorics, topology, and some
parts of statistics, and -after some time - matrix stuff) the most
understandeable parts of maths. It's analysis, differential stuff,
fourier etc. that I could not grasp.
For a lot of people grasping and using seem to be completely different
things. My wife did things with algebra in her university study that I
could only look upon in awe. But she did not realy understand it, she
just used it. She can hardly recall anything of it now. I on the other
hand could do much much less with maths than she could, but I can still
do most of it today, not because I ever used it but because I realy
understood it.
Wouter van Ooijen
-- -------------------------------------------
Van Ooijen Technische Informatica: http://www.voti.nl
consultancy, development, PICmicro products
docent Hogeschool van Utrecht: http://www.voti.nl/hvu
>It's pretty amazing how non-intuitive probability can
>be. When I was in "Mathletes" (competition Math club
>in HS), the probability problems were always the ones
>that resulted in the most discussion.
>I guess this helps explain gambling problems as well...
Seeing as how Dave has said he is doing an Enigma type function, I guess
this is the same maths the Germans used to figure it was unbreakable ...
Just they forgot that some combinations got excluded, and human errors
voided others.
> > It's pretty amazing how non-intuitive probability can be. When
> > I was in "Mathletes" (competition Math club in HS), the probability
> > problems were always the ones that resulted in the most discussion.
> > I guess this helps explain gambling problems as well...
>
> That's why our state lottery is sometimes referred to as a tax on people
> that are bad at math, or a "stupidity tax". Seems to work pretty well. I
> always get a chuckle out of people mentioning that so-and-so won some money
> in the lottery. Please, tell everyone, it will only encourage more to play.
> I love it when other people pay my taxes for me.
I hear that statement a lot, and while I generally agree with it, I think
it only applies to some lottery players.
For example, on the once every year-or-two schedule that I buy a lotto
ticket, I get my dollar's worth out of it in enjoyment, which is to say that
win or lose, the anticipation, daydreams, etc., that the dollar buys are
worth substantially more to me than, say, a candy bar or a cheeseburger,
or any of many other things that that buck would've bought elsewhere.
OTOH, if, as Jeff Foxworthy suggests, your idea of retirement planning
is playing the lottery every week, then...
>At 06:00 AM 4/6/2006, Olin Lathrop wrote:
>
>
>>David VanHorn wrote:
>>
>>
>>>How many different ways are there to arrainge 16 things?
>>>
>>>
>>Imagine what you would do to actually go thru all possible combinations.
>>You grab the first thing, which you can put in 16 different places. The
>>next thing can only go in 15 places, then next in 14, etc. Since this
>>operation comes up a lot, especially in statistics, it is given the special
>>name "factorial", usually written with "!". So the answer to your problem
>>is:
>>
>> 16 factorial = 16! = about 2.09e13
>>
>>
>
>One of the best explanations I've ever seen. You'd probably make a
>great teacher, Olin.
>
>dwayne
>
>
>
I agree, Dwayne. Olin has a real gift for teaching, and a way with words.
>
> It's pretty amazing how non-intuitive probability can be. When
> I was in "Mathletes" (competition Math club in HS), the probability
> problems were always the ones that resulted in the most discussion.
> I guess this helps explain gambling problems as well...
The purpose of the game is to make the odds seem better than they are, or at
least entice you to take a chance.
>
>
> For example, on the once every year-or-two schedule that I buy a lotto
> ticket, I get my dollar's worth out of it in enjoyment, which is to say
> that
> win or lose, the anticipation, daydreams, etc., that the dollar buys are
> worth substantially more to me than, say, a candy bar or a cheeseburger,
> or any of many other things that that buck would've bought elsewhere.
True.. As they say, you can't win if you don't play.
>-----Original Message-----
>From: piclist-bouncesEraseME.....mit.edu [EraseMEpiclist-bouncesmit.edu]
>Sent: 06 April 2006 18:40
>To: Microcontroller discussion list - Public.
>Subject: Re: [PIC]: How many ways
>
>
>
>
>On Thu, 6 Apr 2006, David VanHorn wrote:
>
>> How many different ways are there to arrainge 16 things?
>> I know it's simple, but I can't think of it offhand.
>
>16!
If it's 16 of the same things then only 1 way ;)
Regards
Mike
=======================================================================
This e-mail is intended for the person it is addressed to only. The
information contained in it may be confidential and/or protected by
law. If you are not the intended recipient of this message, you must
not make any use of this information, or copy or show it to any
person. Please contact us immediately to tell us that you have
received this e-mail, and return the original to us. Any use,
forwarding, printing or copying of this message is strictly prohibited.
No part of this message can be considered a request for goods or
services.
=======================================================================
On Thu, 6 Apr 2006 01:41:37 -0400, David VanHorn wrote:
> On 4/6/06, kravnus wolf <RemoveMEkravnusspam_OUTKILLspamyahoo.com> wrote:
> >
> > 16*15*14*13*......*1
>
>
> I thought about that, but the number seemed too large somehow.
> Thanks!
Yes, it *is* very large! Factorials are like that :-)
The general case is nPr, which is the number Permutations of r items from a population of n items.
It's: n!
----------
(n - r)!
When n = r (the case you posed) n - r = 0 and since 0! = 1 it simplifies to n!
On Thu, 6 Apr 2006 16:08:50 +0200, Wouter van Ooijen wrote:
> > If the number seems too large, perhaps it is.
> >(snip)
> > These kinds of problems are generally taught in upper level statistics
> > classes at universities,
>
> No kidding? For me this was part of the exam of the school that preceded
> university (VWO in my country, corresponds to your highschool?). I
> *loved* this subject.
Same here! I did it at "A Level" - our pre-university exams (in those days). I liked it because Statistics
was the subject where you could think through things to get to the answer, if you had time. I found other
types of Maths contained things that you just had to know, and if you didn't, you were lost.
On Thu, 6 Apr 2006 11:13:03 -0400, David VanHorn wrote:
>...
> I got about 8mS to encrypt 32 bytes at 4 MHz, and used reverse lookups so
> that I didn't need to generate forward and reverse tables for the rotors.
Ah, that produces a question: Table lookups where you know the position in the table and want the value there
are trivial in PICs, but how do you do it the other way, where you know the value that's in the table but you
want to find its position? Is it a case of doing a serial search or is there some crafty technique?
I've always been fascinated by codes and cyphers, and particularly Enigma - I've been to Bletchley Park a
number of times. The point that I never understood was how by passing the current there-and-back through the
rotors you could get the appropriate bulb to light - most "explanations" of the workings show connections from
the first rotor to the field of bulbs, but that can't work (the character whose key you were pressing would
light up as well).
I found the answer in a circuit-diagram which showed more than just the rotors, it showed the keys as well.
Each key operates a changeover switch, which in the rest (normally closed) position is connected to the
lightbulb for that character - and in the operated (normally open) position it connects to the power supply.
The common terminal, of course, goes to (/from) the encrypting mechanism. So even if the rest of the wiring
allowed it, this alone makes it impossible to have any character encrypt to itself, which was a key failing
that helped to provide a way to crack it.
>
>
> Ah, that produces a question: Table lookups where you know the position
> in the table and want the value there
> are trivial in PICs, but how do you do it the other way, where you know
> the value that's in the table but you
> want to find its position? Is it a case of doing a serial search or is
> there some crafty technique?
Nothing crafty, just start at the bottom and fetch till you get a match,
while incrementing a counter.
Value of the counter at match is what you want.
Here's the routines. Sorry about the tabbing, studio handles tabs oddly, and
gmail dosen't let me use tabs at all.
Here's rotor 1 forward, the others are same
Nigma1F:
ldi Zh,high(Rotor1*2) ;
ldi ZL,low(rotor1*2) ;
lds TEMP2,R1_Offset ;
rcall Nigma_Fwd ;Forward lookup, output in TEMP
ret
Here's rotor 1 reverse
Nigma1R:
ldi Zh,high(Rotor1*2) ;
ldi ZL,low(rotor1*2) ;
lds TEMP2,R1_Offset ;
rcall Nigma_Rev ;Reverse lookup, what index gives this value?
ret
and the reflector
NigmaRF:
ldi Zh,high(Reflector*2);
ldi ZL,low(Reflector*2) ;
ldi TEMP2,0 ;Reflector dosen't rotate (but it could!)
rcall Nigma_Fwd ;
ret
;
;Forward and reverse table lookups
;
Nigma_Rev:
ldi LOOP,0 ;Start at bottom
Nrev_Loop:
lpm ;LPM pulls up the table value into R0
push TEMP ;
ldi TEMP,$0F ;Remove the distractomatics
and R0,TEMP ;
pop TEMP ;
cp R0,TEMP ;
breq Nrev_Done ;Output is the value in LOOP
inc LOOP ;
adiw ZL,1 ;point to next cell
rjmp Nrev_Loop ;
Nrev_Done:
mov TEMP,LOOP ;
sub TEMP,TEMP2 ;remove offset
andi TEMP,$0F ;
rjmp Nquit ;
;Clear off any evidence
Nquit:
clr R0 ;
clr TEMP2 ;
clr ZL ;
clr ZH ;
clr LOOP ;
ret ;
;
; Don't duplicate any value within a row, and you'll be fine.
; NOTE: The high nybble is only for distraction value.
;
; 0 1 2 3 4 5 6 7 8 9 A B C D E F
Rotor1: .db $03,$bf,$6c,$a1,$fd,$72,$49,$a8,$b4,$65,$40,$46,$f7,$6e,$0B,$6a
Rotor2: .db $b9,$f7,$98,$b6,$94,$62,$2c,$5e,$2a,$c3,$45,$db,$6f,$bd,$b0,$11
Rotor3: .db $74,$bd,$c3,$c5,$2a,$bc,$18,$90,$f1,$07,$39,$2e,$cF,$4b,$f2,$e6
Rotor4: .db $71,$0f,$19,$bb,$e0,$42,$44,$1a,$1c,$0d,$23,$37,$78,$45,$86,$be
;The reflector has to be paired numbers, in that 1 gives you X and X gives
you 1
;
Reflector: .db
$03,$04,$05,$00,$01,$02,$09,$0A,$0B,$06,$07,$08,$0F,$0E,$0D,$0C ;
> Ah, that produces a question: Table lookups where you know
> the position in the table and want the value there
> are trivial in PICs, but how do you do it the other way,
> where you know the value that's in the table but you
> want to find its position? Is it a case of doing a serial
> search or is there some crafty technique?
In an unordened table you just search. If you can specify the order
there is binary searching, hashing, various trees...
Wouter van Ooijen
-- -------------------------------------------
Van Ooijen Technische Informatica: http://www.voti.nl
consultancy, development, PICmicro products
docent Hogeschool van Utrecht: http://www.voti.nl/hvu
>> That's why our state lottery is sometimes referred to as a tax on people
>> that are bad at math, or a "stupidity tax". Seems to work pretty well. I
>> always get a chuckle out of people mentioning that so-and-so won some money
>> in the lottery. Please, tell everyone, it will only encourage more to play.
>> I love it when other people pay my taxes for me.
>
> I hear that statement a lot, and while I generally agree with it, I think
> it only applies to some lottery players.
>
> For example, on the once every year-or-two schedule that I buy a lotto
> ticket, I get my dollar's worth out of it in enjoyment, which is to say that
> win or lose, the anticipation, daydreams, etc., that the dollar buys are
> worth substantially more to me than, say, a candy bar or a cheeseburger,
> or any of many other things that that buck would've bought elsewhere.
Exactly. The simple view of things is only at the probabilities. But this
completely misses the non-linearity of cost and gain. In many contexts, a
rare cost of $1 is considered negligible, whereas a gain of $1M can change
the way a life goes -- or even the gain of merely playing is already worth
it. So multiply that with the appropriate probabilities, and it may start
to make sense :)
The same thing goes for big disasters etc. The cost/gain is in most cases
not linear, so you really need to look at what you are applying the
probabilities.
On Thu, 6 Apr 2006 22:14:02 +0200, Wouter van Ooijen wrote:
I previously wrote:
> > Ah, that produces a question: Table lookups where you know
> > the position in the table and want the value there
> > are trivial in PICs, but how do you do it the other way,
> > where you know the value that's in the table but you
> > want to find its position? Is it a case of doing a serial
> > search or is there some crafty technique?
>
> In an unordened table you just search. If you can specify the order
> there is binary searching, hashing, various trees...
Ah, so the answer to my question is: "No" - there isn't a crafty way to find the position of a given value in
a random-order table, except by searching serially. :-) As we were talking about Enigma rotor-wiring, the
position of the data can't be ordered, or it would be rather easy to decrypt!
Howard Winter wrote:
>> In an unordened table you just search. If you can specify the order
>> there is binary searching, hashing, various trees...
>
> Ah, so the answer to my question is: "No" - there isn't a crafty way to
> find the position of a given value in a random-order table, except by
> searching serially.
Not unless you have some other data structures around the table, like tree
or hash entries as Wouter pointed out.
******************************************************************
Embed Inc, Littleton Massachusetts, (978) 742-9014. #1 PIC
consultant in 2004 program year. http://www.embedinc.com/products
> so the answer to my question is: "No" - there isn't a crafty way to
> find the position of a given value in a random-order table, except by
> searching serially.
In hardware, you have a device called a CAM - Content Addressable
Memory. Very popular in high speed network switches...
>
>
> In hardware, you have a device called a CAM - Content Addressable
> Memory. Very popular in high speed network switches...
That would be a cute thing to have in a processor.
Set two limits, and "give me the address in this range containing this data"
But the sequential read is plenty fast enough for this.
The contents do need to be "random", and even the longest table with 256
elements (assuming you went to 256 position rotors) woudn't take that long
to search.
If, as in the example of the rotors, your random table contains only unique
values in the range 0 through N-1 (or 1 through N), then you simply need
another table of the same size that is the 'inverse' of the first table.
(ie: if the first table has the value M as position N, then the reverse
table has the value N at position M).
On 4/7/06, Robert Ammerman <RemoveMErammermanTakeThisOuTspamverizon.net> wrote:
>
> If, as in the example of the rotors, your random table contains only
> unique
> values in the range 0 through N-1 (or 1 through N), then you simply need
> another table of the same size that is the 'inverse' of the first table.
> (ie: if the first table has the value M as position N, then the reverse
> table has the value N at position M).
Yup, I looked at that implementation as well, but the tables are a pain to
build, and doing two of them that way, felt like a 2^x sort of ickyness.
Doing the reverse lookup was dead easy, and speed is NOT an issue.
I would like to find a way to do those tables in a more automated fashion,
because I'd like to work with some full-byte rotors (0-255) and populating
those with random values, while assuring that no value is repeated, isn't
all that easy.
maybe a small enhancements: 16 DIFFERENT things. If there are some with
the same attribute, then the number decreases, of course. Ad extremum, if
the 16 are the same, then the result is 1.
Regards,
Imre
On Thu, 6 Apr 2006, Peter wrote:
>
>
> On Thu, 6 Apr 2006, David VanHorn wrote:
>
>> How many different ways are there to arrainge 16 things?
>> I know it's simple, but I can't think of it offhand.
>
> 16!
>
> Peter
> --
> On 4/8/06, Robert Ammerman <RemoveMErammermanKILLspamverizon.net> wrote:
>>
>> Generating a random permuttion of the values from 0..N-1 is particularly
>> easy.
>
> Right, but doing it in the assembler at assemble time, or doing it in the
> chip at run time, isn't that simple.
At assembly time you don't do it in assembler. Perl etc.
At run time if you have a source of random numbers you can filter-fill a
vector. E.g. zero the vector then for each random number run through the
vector until you find a non-zero location and put the number in it. If
you find the number in a location before finding a zero discard the
number, and start over with another random number. This gets
prograssively slower (obviously) but that may be good. In fact it it
fills fast, then you know you are using a PRNG ;-)
microbrix.com> wrote:
