[13784] in Perl-Users-Digest
Perl-Users Digest, Issue: 1194 Volume: 9
daemon@ATHENA.MIT.EDU (Perl-Users Digest)
Wed Oct 27 22:57:46 1999
Date: Wed, 27 Oct 1999 19:57:28 -0700 (PDT)
From: Perl-Users Digest <Perl-Users-Request@ruby.OCE.ORST.EDU>
To: Perl-Users@ruby.OCE.ORST.EDU (Perl-Users Digest)
Message-Id: <941079448-v9-i1194@ruby.oce.orst.edu>
Content-Type: text
Perl-Users Digest Wed, 27 Oct 1999 Volume: 9 Number: 1194
Today's topics:
Q: digit-wise number comparisons ? <courcoul@campus.qro.itesm.mx>
Re: Q: digit-wise number comparisons ? (Ilya Zakharevich)
Re: Q: digit-wise number comparisons ? <bivey@teamdev.com>
Re: Q: digit-wise number comparisons ? <lr@hpl.hp.com>
Re: Q: digit-wise number comparisons ? (M.J.T. Guy)
Re: Q: digit-wise number comparisons ? <rhomberg@ife.ee.ethz.ch>
Re: Q: digit-wise number comparisons ? (Bart Lateur)
Re: Q: digit-wise number comparisons ? (M.J.T. Guy)
Re: Q: digit-wise number comparisons ? <guenther@aragorn.it.gac.edu>
Re: Q: digit-wise number comparisons ? (M.J.T. Guy)
Re: Q: digit-wise number comparisons ? (Bart Lateur)
Re: Q: digit-wise number comparisons ? <tye@metronet.com>
Re: Q: digit-wise number comparisons ? <bivey@teamdev.com>
Re: Q: digit-wise number comparisons ? <Tbone@pimpdaddy.com>
Re: Q: digit-wise number comparisons ? <rhomberg@ife.ee.ethz.ch>
Re: Q: digit-wise number comparisons ? <rhomberg@ife.ee.ethz.ch>
Re: Q: digit-wise number comparisons ? <tye@metronet.com>
Re: Q: digit-wise number comparisons ? (Abigail)
Re: Q: digit-wise number comparisons ? <guenther@aragorn.it.gac.edu>
Re: Q: digit-wise number comparisons ? (Ilya Zakharevich)
Re: Q: digit-wise number comparisons ? <lr@hpl.hp.com>
Re: Q: digit-wise number comparisons ? <rootbeer@redcat.com>
Re: Q: digit-wise number comparisons ? <lr@hpl.hp.com>
Re: Q: digit-wise number comparisons ? <dheera@usa.net>
Re: Q: digit-wise number comparisons ? (Ilya Zakharevich)
Re: Q: digit-wise number comparisons ? <tye@metronet.com>
Re: Q: digit-wise number comparisons ? (Ilya Zakharevich)
Re: Q: digit-wise number comparisons ? <Tbone@pimpdaddy.com>
Digest Administrivia (Last modified: 16 Sep 99) (Perl-Users-Digest Admin)
----------------------------------------------------------------------
Date: Mon, 25 Oct 1999 12:30:05 -0500
From: "Juan M. Courcoul" <courcoul@campus.qro.itesm.mx>
Subject: Q: digit-wise number comparisons ?
Message-Id: <3814939D.B63BBFF6@campus.qro.itesm.mx>
In order to assign access controls to a group of people, I need to generate a
largeish (> 1,500) number of random six-digit numerical access codes. Simple
enough; however, I need the codes to differ by at least two digits in any of
the six places.
For example, 348790 and 358790 would be unacceptable, since they only differ in
the second (from left) digit. Likewise for 551308 and 651308, or 739128 and
739138, etc.
Rather than reinvent the wheel, I would like to check first with all you fine
folks on the Perl lists if there's a module or publicly available program to
compare each new code as it is generated, against all the previously assigned
codes and reject those deemed unacceptable. I can keep the previous codes in an
array, a tied hash or whatever, in the generating routine.
TIA for any pointers.
J. Courcoul
Monterrey Tech,
Queretaro Campus
------------------------------
Date: 27 Oct 1999 18:51:34 GMT
From: ilya@math.ohio-state.edu (Ilya Zakharevich)
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <7v7hjm$16g$1@charm.magnus.acs.ohio-state.edu>
[A complimentary Cc of this posting was sent to Philip Guenther
<guenther@aragorn.it.gac.edu>],
who wrote in article <e697lk8iulq.fsf@aragorn.it.gac.edu>:
> > I can even prove what I write above: if the smallest difference between
> > numbers is less than eleven, it is obvious that those numbers differ by
> > only one digit, and I did test all 11th numbers with brute (but smart)
> > force.
>
> Your proof is invalid: differing by 11 is sufficient, but not necessary.
> The set of all multiples of 9 that don't end in 9 is an acceptable set,
> and that's 1/10 of all numbers.
108
198
Hope this helps,
Ilya
------------------------------
Date: 27 Oct 1999 16:19:19 GMT
From: "William" <bivey@teamdev.com>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <01bf2097$3ffc19a0$3527e1ce@bill.jump.net>
M.J.T. Guy <mjtg@cus.cam.ac.uk> wrote in article
<7v7509$aia$1@pegasus.csx.cam.ac.uk>...
> Instead of that, use an xor, with no false negatives. And the way to
> count the number of some character in a string is tr///c. So you
> want (assuming 6 digit numbers)
>
> print "\$a and \$b sufficiently different\n"
> if ((my $x=$a^$b) =~ tr/\0//) < 5;
Did you try this? For example, $a = 438568 and $b = 438566
are unacceptable, but pass your test. (The result of XORing
is 14 which contains less than 5 0s.) Out of a couple of
thousand trials, it didn't find one pair of numbers it
didn't like :-)
But, yeah, tr///c is a good choice. I know why I went
with the original regex: mine would bail out as soon as it
found two non-0s. Useful on long strings, but not really a
factor for 6-digit strings. (I did say there were other
ways.) -Wm
------------------------------
Date: Wed, 27 Oct 1999 09:33:15 -0700
From: Larry Rosler <lr@hpl.hp.com>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <MPG.1280c924b6656a6098a13f@nntp.hpl.hp.com>
In article <01bf2097$3ffc19a0$3527e1ce@bill.jump.net> on 27 Oct 1999
16:19:19 GMT, William <bivey@teamdev.com> says...
> M.J.T. Guy <mjtg@cus.cam.ac.uk> wrote in article
> <7v7509$aia$1@pegasus.csx.cam.ac.uk>...
> > Instead of that, use an xor, with no false negatives. And the way to
> > count the number of some character in a string is tr///c. So you
> > want (assuming 6 digit numbers)
> >
> > print "\$a and \$b sufficiently different\n"
> > if ((my $x=$a^$b) =~ tr/\0//) < 5;
>
> Did you try this? For example, $a = 438568 and $b = 438566
> are unacceptable, but pass your test. (The result of XORing
> is 14 which contains less than 5 0s.) Out of a couple of
> thousand trials, it didn't find one pair of numbers it
> didn't like :-)
The problem with the suggested code is that is xor-ing the bit-
representations of the numbers. What is needed is to xor the decimal
string representations of the numbers.
I showed this in my response in this thread:
my $s = "$x"; # Stringify for string xor.
for (keys %codes) {
$rejects{$x} = 1, next NUM if
# The next line counts the number of different digits.
2 > grep $_ ne "\0" => ($s ^ $_) =~ /(.)/gs;
}
But I didn't think to use tr/// to count the bytes, which is a great
performance improvement.
--
(Just Another Larry) Rosler
Hewlett-Packard Laboratories
http://www.hpl.hp.com/personal/Larry_Rosler/
lr@hpl.hp.com
------------------------------
Date: 27 Oct 1999 16:47:08 GMT
From: mjtg@cus.cam.ac.uk (M.J.T. Guy)
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <7v7aac$ftc$1@pegasus.csx.cam.ac.uk>
In article <01bf2097$3ffc19a0$3527e1ce@bill.jump.net>,
William <bivey@teamdev.com> wrote:
>M.J.T. Guy <mjtg@cus.cam.ac.uk> wrote in article
><7v7509$aia$1@pegasus.csx.cam.ac.uk>...
>> Instead of that, use an xor, with no false negatives. And the way to
>> count the number of some character in a string is tr///c. So you
>> want (assuming 6 digit numbers)
>>
>> print "\$a and \$b sufficiently different\n"
>> if ((my $x=$a^$b) =~ tr/\0//) < 5;
>
>Did you try this? For example, $a = 438568 and $b = 438566
>are unacceptable, but pass your test.
Ooops. Cut and paste cockup. I should have written "xor on _strings_"
instead of "xor". And the correct version of the program (which I had
tested) is
print "\$a and \$b sufficiently different\n"
if ((my $x="$a"^"$b") =~ tr/\0//) < 5;
Mike Guy
------------------------------
Date: Wed, 27 Oct 1999 19:03:57 +0200
From: Alex Rhomberg <rhomberg@ife.ee.ethz.ch>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <3817307D.1521FBE1@ife.ee.ethz.ch>
Tye McQueen wrote:
> Close. Yes, you have 6*9+15*9*9 IDs ruled out by each ID.
> However, the tricky part is figuring out how many of those can
> also be ruled out by how many other IDs.
>
> So I think we can prove that the least dense we can possibly make
> a maximal set is as you outlined [though there may exist no such
> maximal set that is that sparse]. Most maximal sets are much
> more dense.
The best you can do is take every 11th number.
In my test using random numbers, it was really slowing down with >60_000
numbers found.
I can even prove what I write above: if the smallest difference between
numbers is less than eleven, it is obvious that those numbers differ by
only one digit, and I did test all 11th numbers with brute (but smart)
force.
- Alex
------------------------------
Date: Wed, 27 Oct 1999 16:49:01 GMT
From: bart.lateur@skynet.be (Bart Lateur)
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <38172bfc.198718@news.skynet.be>
William wrote:
>Did you try this? For example, $a = 438568 and $b = 438566
>are unacceptable, but pass your test. (The result of XORing
>is 14 which contains less than 5 0s.) Out of a couple of
>thousand trials, it didn't find one pair of numbers it
>didn't like :-)
You should be aware of the fact that bitmise operators bhave differently
for numbers and for strings. So make that $a = "438568" and $b =
"438566". And you should test for null bytes ("\0"), not for "0".
$a = "438568";
$b = "438566";
print join ' ', unpack 'C*', $a ^ $b;
-->
0 0 0 0 0 14
So there are 5 null bytes, and one byte = chr(14).
--
Bart.
------------------------------
Date: 27 Oct 1999 17:28:58 GMT
From: mjtg@cus.cam.ac.uk (M.J.T. Guy)
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <7v7coq$hu5$1@pegasus.csx.cam.ac.uk>
Alex Rhomberg <rhomberg@ife.ee.ethz.ch> wrote:
>
>The best you can do is take every 11th number.
>In my test using random numbers, it was really slowing down with >60_000
>numbers found.
Hardly "the best", since it doesn't make all combinations equally likely.
Abigail showed how to do this properly, with an O(N) algorithm which
ought to have quite a small constant.
Mike Guy
------------------------------
Date: 27 Oct 1999 12:25:37 -0500
From: Philip Guenther <guenther@aragorn.it.gac.edu>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <e697lk8iulq.fsf@aragorn.it.gac.edu>
Alex Rhomberg <rhomberg@ife.ee.ethz.ch> writes:
...
> The best you can do is take every 11th number.
> In my test using random numbers, it was really slowing down with >60_000
> numbers found.
>
> I can even prove what I write above: if the smallest difference between
> numbers is less than eleven, it is obvious that those numbers differ by
> only one digit, and I did test all 11th numbers with brute (but smart)
> force.
Your proof is invalid: differing by 11 is sufficient, but not necessary.
The set of all multiples of 9 that don't end in 9 is an acceptable set,
and that's 1/10 of all numbers. I _think_ that's maximally dense, but I
don't have the time to prove it.
Philip Guenther
----------------------------------------------------------------------
guenther@gac.edu UNIX Systems and Network Administrator
Gustavus Adolphus College St. Peter, MN 56082-1498
Source code never lies: it just misleads (Programming by Purloined Letter?)
------------------------------
Date: 27 Oct 1999 15:16:25 GMT
From: mjtg@cus.cam.ac.uk (M.J.T. Guy)
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <7v7509$aia$1@pegasus.csx.cam.ac.uk>
William <bivey@teamdev.com> wrote:
>
>If you can stand some false negatives, you could try subtracting
>the two numbers and making sure that there are at least two non-0
>digits in the result. (The regex /0*?[^0]0*?[^0]/ is one way, you
>can also take advantage of the fact that the operation should
>drop leading 0s.) If the numbers fail that test, then you
>can take a closer look to recover the good numbers that
>will slip through. (I'm not sure what the yield is, might be
>10% of the numbers get kicked out even though they are usable.)
Instead of that, use an xor, with no false negatives. And the way to
count the number of some character in a string is tr///c. So you
want (assuming 6 digit numbers)
print "\$a and \$b sufficiently different\n"
if ((my $x=$a^$b) =~ tr/\0//) < 5;
Mike Guy
------------------------------
Date: Tue, 26 Oct 1999 18:53:07 GMT
From: bart.lateur@skynet.be (Bart Lateur)
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <3816f78f.1507965@news.skynet.be>
[comp.lang.perl.modules snipped.]
Juan M. Courcoul wrote:
>In order to assign access controls to a group of people, I need to generate a
>largeish (> 1,500) number of random six-digit numerical access codes. Simple
>enough; however, I need the codes to differ by at least two digits in any of
>the six places.
>
>For example, 348790 and 358790 would be unacceptable, since they only differ in
>the second (from left) digit. Likewise for 551308 and 651308, or 739128 and
>739138, etc.
Why don't you do something that banks do with their account numbers,
credit card companies do, and even barcode generation uses: a checksum
of some kind.
A not so uncommon way is to multiply each digit with some number, e.g. 3
for the even and 1 for the odd digits, add the lot together, and
subtract the last digit of the sum from 9. that is what EAN codes
(barcodes) use.
It is just plain impossible for two valid number to be the same except
for one digit.
--
Bart.
------------------------------
Date: 26 Oct 1999 13:19:14 -0500
From: Tye McQueen <tye@metronet.com>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <7v4rb2$s8u@beanix.metronet.com>
) tye@metronet.com writes:
) >I tried for no 3 digits the same, but after about 300 six-digit
) >IDs the search got too slow. I wonder what the sizes are of the
) >largest and smallest sets of 6 digit IDs were no two have 2 (or
) >3) digits in common and no IDs can be added to the set without
) >breaking that property.
Tushar Samant <Tbone@pimpdaddy.com> writes:
) Don't know if I am reading the problem right, but an ID in such
) a set would rule out 6 * 9 ids "around" it which differ from it
) in only one digit, and 15 * 9 ** 2 around those which differ in
) two digits. Which means each ID takes out 1270 out of 10 ** 6,
) giving 787 at most. Don't know how high you can actually go...
Close. Yes, you have 6*9+15*9*9 IDs ruled out by each ID.
However, the tricky part is figuring out how many of those can
also be ruled out by how many other IDs.
So I think we can prove that the least dense we can possibly make
a maximal set is as you outlined [though there may exist no such
maximal set that is that sparse]. Most maximal sets are much
more dense.
For example, if we go to no 3 digits the same, then we have
1+6*9+6*5/2*9*9+6*5/2*4/3*9*9*9 == 15850 IDs ruled out by each
ID which means a maximal set would have at least 63 members.
But picking member candidates at random I usually get about
360-385 members in a maximal set.
--
Tye McQueen Nothing is obvious unless you are overlooking something
http://www.metronet.com/~tye/ (scripts, links, nothing fancy)
------------------------------
Date: 26 Oct 1999 16:30:41 GMT
From: "William" <bivey@teamdev.com>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <01bf1fcf$abb943c0$3527e1ce@bill.jump.net>
"Juan M. Courcoul" <courcoul@campus.qro.itesm.mx> writes:
>In order to assign access controls to a group of people, I need to
generate a
>largeish (> 1,500) number of random six-digit numerical access codes.
Simple
>enough; however, I need the codes to differ by at least two digits in any
of
>the six places.
If you can stand some false negatives, you could try subtracting
the two numbers and making sure that there are at least two non-0
digits in the result. (The regex /0*?[^0]0*?[^0]/ is one way, you
can also take advantage of the fact that the operation should
drop leading 0s.) If the numbers fail that test, then you
can take a closer look to recover the good numbers that
will slip through. (I'm not sure what the yield is, might be
10% of the numbers get kicked out even though they are usable.)
-Wm
------------------------------
Date: 26 Oct 1999 08:08:42 GMT
From: Tushar Samant <Tbone@pimpdaddy.com>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <7v3nia$d92$1@eve.enteract.com>
tye@metronet.com writes:
>I tried for no 3 digits the same, but after about 300 six-digit
>IDs the search got too slow. I wonder what the sizes are of the
>largest and smallest sets of 6 digit IDs were no two have 2 (or
>3) digits in common and no IDs can be added to the set without
>breaking that property.
Don't know if I am reading the problem right, but an ID in such
a set would rule out 6 * 9 ids "around" it which differ from it
in only one digit, and 15 * 9 ** 2 around those which differ in
two digits. Which means each ID takes out 1270 out of 10 ** 6,
giving 787 at most. Don't know how high you can actually go...
------------------------------
Date: Tue, 26 Oct 1999 11:33:39 +0200
From: Alex Rhomberg <rhomberg@ife.ee.ethz.ch>
To: "Juan M. Courcoul" <courcoul@campus.qro.itesm.mx>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <38157573.B20606C@ife.ee.ethz.ch>
Juan M. Courcoul wrote:
>
> In order to assign access controls to a group of people, I need to generate a
> largeish (> 1,500) number of random six-digit numerical access codes. Simple
> enough; however, I need the codes to differ by at least two digits in any of
> the six places.
>
> For example, 348790 and 358790 would be unacceptable, since they only differ in
> the second (from left) digit. Likewise for 551308 and 651308, or 739128 and
> 739138, etc.
Some fun exercise for me...
replace every digit in turn by a 'x', then check if that exists in the
big hash
no guarantees that it works.
I got over 50'000 numbers, the first 20'000 have an average of 2 tries.
#!/usr/bin/perl -w
#use 5.005;
use strict;
my %allhash;
my @nums;
my $wanted = 1500;
while (@nums < $wanted) {
my $num = sprintf "%06d", int rand 1_000_000;
my (@xarray) = map {my $n= $num; substr ($n, $_, 1) = 'x'; $n} (0..5);
next if grep {$_} @allhash{@xarray};#some autovivification
@allhash{@xarray} = map {1} (1..6);
push @nums, $num;
}
#@nums contains them
------------------------------
Date: Tue, 26 Oct 1999 11:42:54 +0200
From: Alex Rhomberg <rhomberg@ife.ee.ethz.ch>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <3815779E.7E495462@ife.ee.ethz.ch>
Tom Phoenix wrote:
>
> On Mon, 25 Oct 1999, Juan M. Courcoul wrote:
>
> > In order to assign access controls to a group of people, I need to
> > generate a largeish (> 1,500) number of random six-digit numerical
> > access codes. Simple enough; however, I need the codes to differ by at
> > least two digits in any of the six places.
> Checking against all previously-generated codes would begin to get slower
> and slower as more codes are generated. Also, if you choose the numbers at
> random, you're almost certain to choose a poor combination which will make
> the future codes harder to find - you'll run out of codes too quickly, in
> other words. If you can find an algorithm in one of those books, it
> shouldn't suffer from these problems.
To get non randomly generated numbers that fit his specification, I'd
suggest taking every eleventh number:
@nums = map {$_*11} (0..$as_many_as_you_want);
But he wanted numbers that are not easily predictable. My test program
gives over 50'000 numbers quickly, with random numbers and checking.
After that, it starts to slow down. I think that not more than
1000000/11 = 90909 numbers are possible, so it's not that bad. Anyway,
with 50'000 numbers used it get's too easyfor the users to guess a
number at random.
- Alex
PS. the prog is now getting slow with 60120 numbers found, and about
3000 tries for a new one...
------------------------------
Date: 25 Oct 1999 23:14:36 -0500
From: Tye McQueen <tye@metronet.com>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <7v39rc$5v3@beanix.metronet.com>
[Posted and e-mailed.]
"Juan M. Courcoul" <courcoul@campus.qro.itesm.mx> writes:
) In order to assign access controls to a group of people, I need to generate a
) largeish (> 1,500) number of random six-digit numerical access codes. Simple
) enough; however, I need the codes to differ by at least two digits in any of
) the six places.
I tried for no 3 digits the same, but after about 300 six-digit
IDs the search got too slow. I wonder what the sizes are of the
largest and smallest sets of 6 digit IDs were no two have 2 (or
3) digits in common and no IDs can be added to the set without
breaking that property.
Anyway, your problem sounded interesting and I had a solution in
just a few minutes so here it is, free and worth every penny. I
added the requirement that IDs can't have leading zeros because
it made sense and saved me from doing C<sprintf>.
My choice of solutions was to have a hash to track each of the
15 possible choices of 4 subdigits and, for each candidate, I made
sure it didn't have a conflict in any of the 15 hashes.
I could have gotten by with, for example, about 7 hashes using
3-digit keys (any number with a conflict in one of the 15 hashes
will also have a conflict in at least 4 others) but that would
have increased the time required for me to write the script much
more than it would have hastened the search for 1500 IDs.
#!/usr/bin/perl -w
use strict;
my @comb;
exit main();
sub find {
my $id= 100_000 + int 900_000*rand;
my @id= split //, $id;
my( $a, $b, $c, $d, $sub );
my $i= 0;
for $a ( 0..2 ) {
for $b ( 1+$a..3 ) {
for $c ( 1+$b..4 ) {
for $d ( 1+$c..5 ) {
$sub= join "", @id[$a,$b,$c,$d];
if( $comb[$i]->{$sub} ) {
#warn "Rejected $id: too similar to ",
# $comb[$i]->{$sub}, " [index $i=$a,$b,$c,$d]\n";
return -$id;
}
$i++;
}
}
}
}
$i= 0;
for $a ( 0..2 ) {
for $b ( 1+$a..3 ) {
for $c ( 1+$b..4 ) {
for $d ( 1+$c..5 ) {
$sub= join "", @id[$a,$b,$c,$d];
$comb[$i]->{$sub}= $id;
$i++;
}
}
}
}
return $id;
}
sub main {
my $need= 15000;
my $rejects= 0;
my @found;
while( @found < $need ) {
my $next= find();
if( 0 < $next ) {
warn "Found $next (",0+@found," of $need, $rejects rejects).\n";
push @found, $next;
$rejects= 0;
} else {
$rejects++;
}
}
return 0;
}
--
Tye McQueen Nothing is obvious unless you are overlooking something
http://www.metronet.com/~tye/ (scripts, links, nothing fancy)
------------------------------
Date: 26 Oct 1999 00:45:04 -0500
From: abigail@delanet.com (Abigail)
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <slrn81afu6.fji.abigail@alexandra.delanet.com>
Juan M. Courcoul (courcoul@campus.qro.itesm.mx) wrote on MMCCXLVI
September MCMXCIII in <URL:news:3814939D.B63BBFF6@campus.qro.itesm.mx>:
\\ In order to assign access controls to a group of people, I need to generate a
\\ largeish (> 1,500) number of random six-digit numerical access codes. Simple
\\ enough; however, I need the codes to differ by at least two digits in any of
\\ the six places.
\\
\\ For example, 348790 and 358790 would be unacceptable, since they only differ
\\ the second (from left) digit. Likewise for 551308 and 651308, or 739128 and
\\ 739138, etc.
\\
\\ Rather than reinvent the wheel, I would like to check first with all you fine
\\ folks on the Perl lists if there's a module or publicly available program to
\\ compare each new code as it is generated, against all the previously assigned
\\ codes and reject those deemed unacceptable. I can keep the previous codes in
\\ array, a tied hash or whatever, in the generating routine.
\\
\\ TIA for any pointers.
#!/opt/perl/bin/perl -w
use strict;
my %hash;
my $n;
MAIN:
while ($n = <DATA>) {
chomp $n;
my @t = map {my $t = $n; substr $t, $_ - 1, 1, '.'; $t} 1 .. 6;
foreach my $t (@t) {
if (exists $hash {$t}) {
print "$n is not allowed ($hash{$t})\n";
next MAIN;
}
}
@hash {@t} = ($n) x 6;
print "$n is allowed\n";
}
__DATA__
123456
123457
123467
123467
124467
824467
This would be O (N * M * U) if you have N strings of size M, where each
character can have U values.
For fixed M and U, as in your case, that's O (N).
Abigail
--
%0=map{reverse+chop,$_}ABC,ACB,BAC,BCA,CAB,CBA;$_=shift().AC;1while+s/(\d+)((.)
(.))/($0=$1-1)?"$0$3$0{$2}1$2$0$0{$2}$4":"$3 => $4\n"/xeg;print#Towers of Hanoi
-----------== Posted via Newsfeeds.Com, Uncensored Usenet News ==----------
http://www.newsfeeds.com The Largest Usenet Servers in the World!
------== Over 73,000 Newsgroups - Including Dedicated Binaries Servers ==-----
------------------------------
Date: 25 Oct 1999 19:45:15 -0500
From: Philip Guenther <guenther@aragorn.it.gac.edu>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <e69904rhrvo.fsf@aragorn.it.gac.edu>
"Juan M. Courcoul" <courcoul@campus.qro.itesm.mx> writes:
>
>In order to assign access controls to a group of people, I need to
>generate a largeish (> 1,500) number of random six-digit numerical
>access codes. Simple enough; however, I need the codes to differ by at
>least two digits in any of the six places.
Do you mean that they must differ by at least one in each of two digit
places, that they must differ by at two in one digit place, or that they
must differ by at least two in each of two digit places? Your example
all eliminate differing by one in one digit place, but since you never
give an example of two valid codes, it's hard to tell which of the above
you mean.
If you mean the first of the options, such that, say, 551308 and 651208
would be fine, then an easy strategy would be do pick random five digit
numbers, check their uniqueness, then add a digit from the range 0-8 on
the right to make the number divisible by nine. This will guarantee
that any two final numbers will differ by at least one in at least two
places.
Philip Guenther
----------------------------------------------------------------------
guenther@gac.edu UNIX Systems and Network Administrator
Gustavus Adolphus College St. Peter, MN 56082-1498
Source code never lies: it just misleads (Programming by Purloined Letter?)
------------------------------
Date: 26 Oct 1999 01:32:46 GMT
From: ilya@math.ohio-state.edu (Ilya Zakharevich)
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <7v30bu$sia$1@charm.magnus.acs.ohio-state.edu>
[A complimentary Cc of this posting was sent to Juan M. Courcoul
<courcoul@campus.qro.itesm.mx>],
who wrote in article <3814939D.B63BBFF6@campus.qro.itesm.mx>:
> In order to assign access controls to a group of people, I need to generate a
> largeish (> 1,500) number of random six-digit numerical access codes. Simple
> enough; however, I need the codes to differ by at least two digits in any of
> the six places.
Well, I realized that there is a very simple solution:
perl -wle "$shift = 3; $max = 1 + int((1e6-$shift)/11); $ids = 1500; \
while ($ids) { \
$id = int rand $max; \
redo if $s{$id}++; \
printf qq(%06d\n), 11*$id+$shift; \
$ids--}"
One may think that this increases a risk of somebody guessing ids, but
in fact it is exactly to opposite: since all the ids give remainder 3
in division by 11, and it it is "easy" to guess looking on several
ids, then a smart-alek intruder may try to guess id by choosing ids
with give remainder 3 in division by 11 (to reduce the search time).
But the system could easily detect that erroneous ids have suspiciously
often a correct remainder, thus detect an attempt of intrusion.
Ilya
------------------------------
Date: Mon, 25 Oct 1999 16:22:45 -0700
From: Larry Rosler <lr@hpl.hp.com>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <MPG.127e8622fe3cad8b98a125@nntp.hpl.hp.com>
In article <MPG.127e73b1ec121d598a123@nntp.hpl.hp.com> on Mon, 25 Oct
1999 15:04:08 -0700, Larry Rosler <lr@hpl.hp.com> says...
> In article <3814939D.B63BBFF6@campus.qro.itesm.mx> on Mon, 25 Oct 1999
> 12:30:05 -0500, Juan M. Courcoul <courcoul@campus.qro.itesm.mx> says...
> > In order to assign access controls to a group of people, I need to generate a
> > largeish (> 1,500) number of random six-digit numerical access codes. Simple
> > enough; however, I need the codes to differ by at least two digits in any of
> > the six places.
> >
> > For example, 348790 and 358790 would be unacceptable, since they only differ in
> > the second (from left) digit. Likewise for 551308 and 651308, or 739128 and
> > 739138, etc.
I think I offered a solution to the wrong problem. The solution I
posted prepares numbers that differ in at least two of the six places.
But reading Ilya's solution and looking back here makes me think the
solution requested is for numbers that differ by at least two digit
values in any one of the six places.
I would replace the inner test by a loop over all six characters,
comparing abs(ord($s, 0, $i) - ord($_, 0, $1)) to 2. This is even
slower than the other solution.
> Is there a better way, short of doing the research that Tom Phoenix
> suggests?
I think Ilya's constructive approach is much better!
--
(Just Another Larry) Rosler
Hewlett-Packard Laboratories
http://www.hpl.hp.com/personal/Larry_Rosler/
lr@hpl.hp.com
------------------------------
Date: Mon, 25 Oct 1999 14:25:27 -0700
From: Tom Phoenix <rootbeer@redcat.com>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <Pine.GSO.4.10.9910251420470.29843-100000@user2.teleport.com>
On Mon, 25 Oct 1999, Juan M. Courcoul wrote:
> In order to assign access controls to a group of people, I need to
> generate a largeish (> 1,500) number of random six-digit numerical
> access codes. Simple enough; however, I need the codes to differ by at
> least two digits in any of the six places.
This is a problem from the domain of error-correcting codes. I seem to
recall that there are efficient algorithms for producing large lists of
such codes, but I have none of them at hand today. You should probably
check in a good library for books on error-correcting codes and related
issues.
> Rather than reinvent the wheel, I would like to check first with all
> you fine folks on the Perl lists if there's a module or publicly
> available program to compare each new code as it is generated, against
> all the previously assigned codes and reject those deemed
> unacceptable.
Checking against all previously-generated codes would begin to get slower
and slower as more codes are generated. Also, if you choose the numbers at
random, you're almost certain to choose a poor combination which will make
the future codes harder to find - you'll run out of codes too quickly, in
other words. If you can find an algorithm in one of those books, it
shouldn't suffer from these problems.
Good luck!
--
Tom Phoenix Perl Training and Hacking Esperanto
Randal Schwartz Case: http://www.rahul.net/jeffrey/ovs/
------------------------------
Date: Mon, 25 Oct 1999 15:04:08 -0700
From: Larry Rosler <lr@hpl.hp.com>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <MPG.127e73b1ec121d598a123@nntp.hpl.hp.com>
In article <3814939D.B63BBFF6@campus.qro.itesm.mx> on Mon, 25 Oct 1999
12:30:05 -0500, Juan M. Courcoul <courcoul@campus.qro.itesm.mx> says...
> In order to assign access controls to a group of people, I need to generate a
> largeish (> 1,500) number of random six-digit numerical access codes. Simple
> enough; however, I need the codes to differ by at least two digits in any of
> the six places.
>
> For example, 348790 and 358790 would be unacceptable, since they only differ in
> the second (from left) digit. Likewise for 551308 and 651308, or 739128 and
> 739138, etc.
>
> Rather than reinvent the wheel, I would like to check first with all you fine
> folks on the Perl lists if there's a module or publicly available program to
> compare each new code as it is generated, against all the previously assigned
> codes and reject those deemed unacceptable. I can keep the previous codes in an
> array, a tied hash or whatever, in the generating routine.
>
> TIA for any pointers.
I have no pointers to modules, and only a quadratic approach to offer,
which is less than satisfying. However...
I would keep the existing codes as keys in an hash, for lack of a more
useful key for later lookup. That is why the solution is quadratic.
The hash serves only to immediately eliminate numbers already generated,
without having to scan the entire list.
{ my (%codes, %rejects); # Private hashes.
sub new_code {
NUM: {
my $x = 100000 + int rand 900000;
$rejects{$x} = 1, next NUM if exists $codes{$x};
next NUM if exists $rejects{$x};
my $s = "$x"; # Stringify for string xor.
for (keys %codes) {
$rejects{$x} = 1, next NUM if
# The next line counts the number of different digits.
2 > grep $_ ne "\0" => ($s ^ $_) =~ /(.)/gs;
}
$codes{$x} = 1; # The hash keys are now stringified.
return $x;
}
} }
The search space can be reduced by two-thirds by using instead a hash of
lists, where the hash key is 10 plus the sum of the six digits in the
numbers and each list is the list of numbers which have that sum. Now
only those hashes need be searched whose sums are within 9 on each side
of the sum of the new candidate number. (Any number whose sum is further
away necessarily differs in at least two digits.) Thus only 19 of the
60 sublists need be searched. But this is nevertheless quadratic.
Is there a better way, short of doing the research that Tom Phoenix
suggests?
--
(Just Another Larry) Rosler
Hewlett-Packard Laboratories
http://www.hpl.hp.com/personal/Larry_Rosler/
lr@hpl.hp.com
------------------------------
Date: Mon, 25 Oct 1999 22:17:07 GMT
From: Dheera <dheera@usa.net>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <7v2kt0$r55$1@nnrp1.deja.com>
I don't know of any module to do this, but the answer would probably be
quite simple. Assuming there are two strings $x and $y, which contain
the codes.... $x and $y should be the same string length.
$c=0;
if(length($x)==length($y)) {
for($i=0;$i<length($x);$i++) {
if(substr($x,$i,1)==substr($y,$i,1)) {
$c++;
}
}
}
if($c>=2) {
// the codes are valid
}
In article <3814939D.B63BBFF6@campus.qro.itesm.mx>,
"Juan M. Courcoul" <courcoul@campus.qro.itesm.mx> wrote:
> In order to assign access controls to a group of people, I need to
generate a
> largeish (> 1,500) number of random six-digit numerical access codes.
Simple
> enough; however, I need the codes to differ by at least two digits in
any of
> the six places.
>
> For example, 348790 and 358790 would be unacceptable, since they only
differ in
> the second (from left) digit. Likewise for 551308 and 651308, or
739128 and
> 739138, etc.
>
> Rather than reinvent the wheel, I would like to check first with all
you fine
> folks on the Perl lists if there's a module or publicly available
program to
> compare each new code as it is generated, against all the previously
assigned
> codes and reject those deemed unacceptable. I can keep the previous
codes in an
> array, a tied hash or whatever, in the generating routine.
>
> TIA for any pointers.
>
> J. Courcoul
> Monterrey Tech,
> Queretaro Campus
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: 25 Oct 1999 22:38:34 GMT
From: ilya@math.ohio-state.edu (Ilya Zakharevich)
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <7v2m5a$gdd$1@charm.magnus.acs.ohio-state.edu>
[A complimentary Cc of this posting was sent to Juan M. Courcoul
<courcoul@campus.qro.itesm.mx>],
who wrote in article <3814939D.B63BBFF6@campus.qro.itesm.mx>:
> In order to assign access controls to a group of people, I need to generate a
> largeish (> 1,500) number of random six-digit numerical access codes. Simple
> enough; however, I need the codes to differ by at least two digits in any of
> the six places.
As other people mentioned, in general it bounds to be NP. But with a
tiny number of people you have, it is quite easy.
Simple example: assign the first 1000 codes of the form abcabc, (as in
123123), the other 1000 codes of the form abcdef, here def = abc +
222. You can easily obfuscate this if needed: break 1000 of 3-digit
combinations into 500 pairs of 3-digit combinations aN, bN (N=1..500)
such that aN differs from bN at least in two digits. Similarly,
create pairs cN, dN. Then you get 2000 combinations of the form
aN cN
bN cN
aN dN
bN dN
with N=1..500.
Ilya
------------------------------
Date: 27 Oct 1999 16:49:48 -0500
From: Tye McQueen <tye@metronet.com>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <7v7s1s$6dj@beanix.metronet.com>
Alex Rhomberg <rhomberg@ife.ee.ethz.ch> writes:
)
) The best you can do is take every 11th number.
) In my test using random numbers, it was really slowing down with >60_000
) numbers found.
No, you can get even denser. You can use 1/10 of the space, not
just 1/11. For example, you add 11 nine times, then add 1, add 11
nine times, add 1, etc:
for $i ( 1000..9999 ) {
for $j( 0..9 ) {
print "$i$j$j\n";
}
}
100000
100011
100022
100033
...
100099
100100
Or you can add 9 each time and let 1/10 of those be rejected.
I won't guarantee that is the densest, but it feels like it is.
--
Tye McQueen Nothing is obvious unless you are overlooking something
http://www.metronet.com/~tye/ (scripts, links, nothing fancy)
------------------------------
Date: 27 Oct 1999 23:10:04 GMT
From: ilya@math.ohio-state.edu (Ilya Zakharevich)
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <7v80oc$gl4$1@charm.magnus.acs.ohio-state.edu>
[A complimentary Cc of this posting was sent to Tye McQueen
<tye@metronet.com>],
who wrote in article <7v7s1s$6dj@beanix.metronet.com>:
> No, you can get even denser. You can use 1/10 of the space, not
> just 1/11. For example, you add 11 nine times, then add 1, add 11
> nine times, add 1, etc:
>
> for $i ( 1000..9999 ) {
> for $j( 0..9 ) {
> print "$i$j$j\n";
> }
> }
>
> 100000
> ...
> 100100
Look on these two.
If my vague memory from my highschool days is correct, "each 11th" is
the densest possible packing - with an exception that sometimes one
can put *one* additional number.
Ilya
------------------------------
Date: 27 Oct 1999 23:19:50 GMT
From: Tushar Samant <Tbone@pimpdaddy.com>
Subject: Re: Q: digit-wise number comparisons ?
Message-Id: <7v81am$ckk$1@eve.enteract.com>
tye@metronet.com writes:
>Tushar Samant <Tbone@pimpdaddy.com> writes:
>) Don't know if I am reading the problem right, but an ID in such
>) a set would rule out 6 * 9 ids "around" it which differ from it
>) in only one digit, and 15 * 9 ** 2 around those which differ in
>) two digits. Which means each ID takes out 1270 out of 10 ** 6,
>) giving 787 at most. Don't know how high you can actually go...
>
>Close. Yes, you have 6*9+15*9*9 IDs ruled out by each ID.
>However, the tricky part is figuring out how many of those can
>also be ruled out by how many other IDs.
D'OH!
------------------------------
Date: 16 Sep 99 21:33:47 GMT (Last modified)
From: Perl-Users-Request@ruby.oce.orst.edu (Perl-Users-Digest Admin)
Subject: Digest Administrivia (Last modified: 16 Sep 99)
Message-Id: <null>
Administrivia:
The Perl-Users Digest is a retransmission of the USENET newsgroup
comp.lang.perl.misc. For subscription or unsubscription requests, send
the single line:
subscribe perl-users
or:
unsubscribe perl-users
to almanac@ruby.oce.orst.edu.
| NOTE: The mail to news gateway, and thus the ability to submit articles
| through this service to the newsgroup, has been removed. I do not have
| time to individually vet each article to make sure that someone isn't
| abusing the service, and I no longer have any desire to waste my time
| dealing with the campus admins when some fool complains to them about an
| article that has come through the gateway instead of complaining
| to the source.
To submit articles to comp.lang.perl.announce, send your article to
clpa@perl.com.
To request back copies (available for a week or so), send your request
to almanac@ruby.oce.orst.edu with the command "send perl-users x.y",
where x is the volume number and y is the issue number.
For other requests pertaining to the digest, send mail to
perl-users-request@ruby.oce.orst.edu. Do not waste your time or mine
sending perl questions to the -request address, I don't have time to
answer them even if I did know the answer.
------------------------------
End of Perl-Users Digest V9 Issue 1194
**************************************
