Searching \ for '[PIC]: How many ways' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/microchip/devices.htm?key=pic
Search entire site for: 'How many ways'.

Exact match. Not showing close matches.
PICList Thread
'[PIC]: How many ways'
2006\04\06@011439 by David VanHorn

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

picon face
16*15*14*13*......*1

john

--- David VanHorn <spam_OUTdvanhornTakeThisOuTspammicrobrix.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

picon face
On 4/6/06, kravnus wolf <.....kravnusKILLspamspam@spam@yahoo.com> wrote:
>
> 16*15*14*13*......*1
>
> john
>
> --- David VanHorn <dvanhornspamKILLspammicrobrix.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

picon face
On 4/6/06, kravnus wolf <.....kravnusKILLspamspam.....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
picon face
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}

2006\04\06@021140 by Wouter van Ooijen

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

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

picon face
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 <dvanhornspamspam_OUTmicrobrix.com> wrote:

{Quote hidden}

> --

2006\04\06@075815 by olin piclist

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

face picon face
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 <KILLspamdvanhornKILLspamspammicrobrix.com> wrote:
> On 4/6/06, kravnus wolf <RemoveMEkravnusTakeThisOuTspamyahoo.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

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

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

flavicon
face
In Argentina this is teached in 2nd year of engeneering.

Mauricio Jancic
Janso Desarrollos
http://www.janso.com.ar
spamBeGoneinfospamBeGonespamjanso.com.ar
(54) 11-4542-3519


> {Original Message removed}

2006\04\06@111305 by David VanHorn

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

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

flavicon
face
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   <TakeThisOuTdwaynerEraseMEspamspam_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

face picon face

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

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

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

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

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

face picon face
Dwayne Reid wrote:

{Quote hidden}

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
RemoveMEattachspamTakeThisOuTengineer.cotse.net .
1-520-850-1673 USA/Canada
http://beam.to/azengineer

2006\04\06@125247 by David VanHorn

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

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

picon face


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

picon face


>-----Original Message-----
>From: piclist-bouncesEraseMEspam.....mit.edu [EraseMEpiclist-bouncesspammit.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

face picon face
Except in a two or more dimension ordering system... :-)

-Adam

On 4/6/06, Michael Rigby-Jones <RemoveMEMichael.Rigby-JonesEraseMEspamEraseMEbookham.com> wrote:
> If it's 16 of the same things then only 1 way ;)

2006\04\06@143309 by Howard Winter

face
flavicon
picon face
Dave,

On Thu, 6 Apr 2006 01:41:37 -0400, David VanHorn wrote:

> On 4/6/06, kravnus wolf <RemoveMEkravnusspam_OUTspamKILLspamyahoo.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

face
flavicon
picon face
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

face
flavicon
picon face
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

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

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

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

face
flavicon
picon face
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

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

face picon face

> 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

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

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

picon face
On 4/7/06, Robert Ammerman <RemoveMErammermanTakeThisOuTspamspamverizon.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

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

picon face
On 4/8/06, Robert Ammerman <EraseMErammermanspamspamspamBeGoneverizon.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

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

picon face


On Sat, 8 Apr 2006, David VanHorn wrote:

> On 4/8/06, Robert Ammerman <RemoveMErammermanKILLspamspamverizon.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...