Exact match. Not showing close matches.
PICList
Thread
'[PIC]: How many ways'
2006\04\06@011439
by
David VanHorn
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
2006\04\06@013326
by
kravnus wolf
16*15*14*13*......*1
john
--- David VanHorn <spam_OUTdvanhornTakeThisOuT
microbrix.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
> --
2006\04\06@014106
by
David VanHorn
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
> > --
2006\04\06@014137
by
David VanHorn
On 4/6/06, kravnus wolf <.....kravnusKILLspam.....yahoo.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
2006\04\06@020923
by
Robert Rolf
And on your handy scientific calculator (winblows even) 16!.
16 factorial (n!). That's why the function exists. About 2E13.
R
David VanHorn wrote:
{Quote hidden}> 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
2006\04\06@021140
by
Wouter van Ooijen
> How many different ways are there to arrainge 16 things?
> I know it's simple, but I can't think of it offhand.
16!, assuming all things are different.
first you pick 1 from 16 for the first place, then you pick 1 from 15
for the second place, etc.
Wouter van Ooijen
-- -------------------------------------------
Van Ooijen Technische Informatica: http://www.voti.nl
consultancy, development, PICmicro products
docent Hogeschool van Utrecht: http://www.voti.nl/hvu
2006\04\06@030051
by
David VanHorn
>
> 16!, assuming all things are different.
>
> first you pick 1 from 16 for the first place, then you pick 1 from 15
> for the second place, etc.
That's what I was looking for, like drawing cards or wiring enigma rotors.
--
> Feel the power of the dark side! Atmel AVR
2006\04\06@032219
by
kravnus wolf
this branch of maths is factorial, but the important
thing is not the symbols but the idea :)
the piclist is always read to help each other :D
john
--- David VanHorn <dvanhornspam_OUTmicrobrix.com> wrote:
{Quote hidden}> 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
> --
2006\04\06@075815
by
olin piclist
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
2006\04\06@093759
by
M. Adam Davis
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.
Perhaps you are looking into producing a sudoku generator?
http://www.knowing.net/hexodoku/
-Adam
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
> -
2006\04\06@100854
by
Wouter van Ooijen
> 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
2006\04\06@101938
by
olin piclist
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
2006\04\06@102946
by
Mauricio Jancic
2006\04\06@111305
by
David VanHorn
|
>
> Perhaps you are looking into producing a sudoku generator?
> http://www.knowing.net/hexodoku/
no, but interesting.
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.
--
> Feel the power of the dark side! Atmel AVR
2006\04\06@111424
by
David VanHorn
>
> Yeah, I remember that we did pretty much this same problem (with fewer
> items) in 7th or 8th grade. This is really basic math.
Yes, it is, 6th grade for me, but I couldn't recall it at the right moment
last night.
--
> Feel the power of the dark side! Atmel AVR
2006\04\06@112836
by
Dwayne Reid
|
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
--
Dwayne Reid <TakeThisOuTdwaynerEraseMEspam_OUTplanet.eon.net>
Trinity Electronics Systems Ltd Edmonton, AB, CANADA
(780) 489-3199 voice (780) 487-6397 fax
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.
2006\04\06@113851
by
William Chops Westfield
On Apr 6, 2006, at 6:37 AM, M. Adam Davis wrote:
> 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...
BillW
2006\04\06@115755
by
olin piclist
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
2006\04\06@120627
by
Wouter van Ooijen
> 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
2006\04\06@120836
by
Alan B. Pearce
>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.
2006\04\06@121447
by
Mike Hord
|
> > 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...
Mike H.
2006\04\06@123645
by
Bob Axtell
Dwayne Reid wrote:
{Quote hidden}>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.
--Bob
--
Note: To protect our network,
attachments must be sent to
RemoveMEattachTakeThisOuTengineer.cotse.net .
1-520-850-1673 USA/Canada
http://beam.to/azengineer
2006\04\06@125247
by
David VanHorn
>
> 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.
--
> Feel the power of the dark side! Atmel AVR
2006\04\06@125504
by
David VanHorn
>
>
> 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.
--
> Feel the power of the dark side! Atmel AVR
2006\04\06@134022
by
Peter
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
2006\04\06@134920
by
Michael Rigby-Jones
|
>-----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.
=======================================================================
2006\04\06@140019
by
M. Adam Davis
2006\04\06@143309
by
Howard Winter
Dave,
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!
Cheers,
Howard Winter
St.Albans, England
2006\04\06@145008
by
Howard Winter
Wouter,
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.
Cheers,
Howard Winter
St.Albans, England
2006\04\06@151438
by
Howard Winter
Dave,
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.
Cheers,
Howard Winter
St.Albans, England
2006\04\06@153450
by
David VanHorn
|
|
>
>
> 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 ;
Nigma_Fwd:
add TEMP2,TEMP ;Rotor position + char mod 15
andi TEMP2,$0F ;
add ZL,TEMP2 ;
adc ZH,ZERO ;
lpm ;
mov TEMP,R0 ;
andi TEMP,$0F ;Obscuration
;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 ;
--
Feel the power of the dark side! Atmel AVR
2006\04\06@161403
by
Wouter van Ooijen
> 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
2006\04\06@204354
by
Gerhard Fiedler
|
Mike Hord wrote:
>> 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.
Gerhard
2006\04\07@081221
by
Howard Winter
Wouter,
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!
Cheers,
Howard Winter
St.Albans, England
2006\04\07@082138
by
olin piclist
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
2006\04\07@105602
by
William Chops Westfield
> 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...
BillW
2006\04\07@113156
by
David VanHorn
>
>
> 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.
--
Feel the power of the dark side! Atmel AVR
2006\04\07@234346
by
Robert Ammerman
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).
Bob Ammerman
RAm Systems
{Original Message removed}
2006\04\08@014834
by
David VanHorn
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.
--
> Feel the power of the dark side! Atmel AVR
2006\04\08@193412
by
Robert Ammerman
Generating a random permuttion of the values from 0..N-1 is particularly
easy.
Assuming that you have a good source of 'random numbers', then you can
simply:
unsigned char a[N];
for ( i=n-1; i >0; --i )
{
j = random value in range 0..i
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
And creating the reversed table is also very simple:
unsigned char b[N];
for (i=0; i < N; ++i)
{
b[ a[i] ] = i;
}
Bob Ammerman
RAm Systems
2006\04\08@220543
by
David VanHorn
On 4/8/06, Robert Ammerman <EraseMErammermanspamspamBeGoneverizon.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.
--
> Feel the power of the dark side! Atmel AVR
2006\04\09@113412
by
dr. Imre Bartfai
Hi,
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
> --
2006\04\10@164955
by
Peter
On Sat, 8 Apr 2006, David VanHorn wrote:
> 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 ;-)
Peter
More... (looser matching)
- Last day of these posts
- In 2006
, 2007 only
- Today
- New search...
