HDTenEightyP/NetNews huggingface dataset:
From: dougm@titan.cs.rice.edu (Doug Moore)
Subject: Re: Looking for random permutation generation algorithms
Organization: Rice University Computer Science, Houston, Texas
	<1993Jan8.163909.20820@cs.cornell.edu>
	<1993Jan8.172824.22910@cs.cornell.edu>
Date: Fri, 8 Jan 1993 22:17:07 GMT

Now that the problem of computing a 1-1 mapping from the integers 0 <=
i < n! to permuatations of n elements has been solved, can anyone
suggest a way to compute a function f(i,j), 0 <= i < n!, 0 <= j < n,
such that f(i,j) is the jth component of the ith permutation IN
CONSTANT SPACE?  Personally, I can't.  Maybe it's impossible.

An application?  Suppose you wanted to implement a truly uniform
open-addressed hashing scheme.  The algorithms proposed so far will
generate a permutation (probe sequence) from a key, but require linear
additional space to do it.  That would not be acceptible for a large
hash table.  Any ideas?

Doug Moore
(dougm@cs.rice.edu)
Newsgroups: comp.theory
From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
Subject: Re: Looking for random permutation generation algorithms
Organization: Computer Science Department,  Stanford University.
Date: Sat, 9 Jan 1993 23:46:06 GMT

In article <24824@galaxy.ucr.edu> marek@wigry.ucr.edu (marek chrobak) writes:
>In article <1993Jan8.210013.24614@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
>>But for N >> M it has two drawbacks: the time to initialize the array,
>>and the space required for it, both being O(N).  In contrast Floyd's
>>method requires space O(M) and time somewhere between O(M) and O(M^2)
>>depending on the method used to test for repetitions.  (For N some
>>modest multiple of M one might instead keep track of repetitions using
>>an array of N bits, i.e. N/8 bytes, initialized to 0.)
>
>This method also can be implemented in O(M) space and O(M logM) time.
>
>The general idea is that there is no need to initialize and maintain
>the whole array. Only M entries can be changed, so for other entries
>A[i] = i. Use any balanced search tree for storing needed information.
>For details see: Chrobak, Harter, A note on random sampling, Information
>Processing Letters 29 (1988) 255-256.

Quite right, I'd entirely forgotten that option was available.  It
dates back at least to the 70's though it would take me a while to dig
up an instance.

This rather undermines the rationale Bentley offered for Floyd's
algorithm, at least for permutations, where I don't right now see any
big advantage of either algorithm over the other.  Simulating A[i]=i
with any prescribed amount of time and storage is essentially identical
in difficulty to inserting a default output ahead of K in Floyd's
algorithm under the same prescription.

The interest in Floyd's algorithm (besides its ingenuity) therefore
would seem to be its greater applicability, namely to the problem of
sampling combinations.  Here the storage requirement is only N bits,
which for N < M log_2 M would seem close to unbeatable.
-- 
Vaughan Pratt				There's safety in certain numbers.
Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
From: rolfe@dsuvax.dsu.edu (Tim Rolfe)
Subject: Re: Looking for random permutation generation algorithms
Organization: Dakota State University
Date: Wed, 6 Jan 1993 22:48:04 GMT

In <1993Jan6.014749.15323@ee.ubc.ca> rayw@ee.ubc.ca (raymond w m woo) writes:

>Hi, does anyone know, or can provide any pointer in the literature to, any 
>random permutation generation algorithm that can be easily implemented as a 
>function in a computer program?  

>Ideally, this function would be computationally effective, and the input 
>that this function takes would be some kind of index/rank number of the
>permution to be generated.  
[...]

One approach is to consider the offset calculation for an N-dimensional
array with dimensions (N, N-1, ... , 2, 1).  Language purists:  forgive
the language in what follows --- I mis-remembered the question as from
comp.lang.fortran when I worked up the answering code.  I'm assuming
enough Fortran knowledge to do the translation into <current hot lang.>.

      subroutine GenPrm (IdxVal, N, Set)
*
* Permutations of N items can be indexed uniquely after the fashion of
* the array off-set calculation for a multidimensional array of dimension
* (N,N-1,N-2,...,2,1)
*
* E.g., if N = 4, offset (column major) is I1*3! + I2*2! + I3*1! + I4
*
      integer IdxVal, N
      integer Set(*)
      integer Idx, Jdx, Work, Temp
      integer OldN, OverFl
      data OldN/-1/
      save OldN, OverFl
*
      if (N .ne. OldN) then
         OldN = N
         OverFl = 1
         do 10 Idx = 2, N
            OverFl = OverFl * Idx
   10    continue
      end if
*
* (1) Initialize the "Set" array with values to be permuted
*
      do 20 Idx = 1, N
         Set(Idx) = Idx
   20 continue
*
* (2) Set up to strip out the "Indices" in the multidimensional reference
*
      Work = mod (IdxVal, OverFl)
      Ndx  = OverFl/N
*
* (3) Isolate those Indexes
*
      do 30 Idx = 1, N-1
         Jdx = Idx + Work / Ndx
         Work = mod (Work, Ndx)
         Ndx = Ndx / (N-Idx)
         Temp = Set(Idx)
         Set(Idx) = Set(Jdx)
         Set(Jdx) = Temp
   30 continue
      end
*
      program TestBed
      parameter (N = 4)
      integer   Set(N)
      integer   Idx, Lim, Tst
      character OutFmt*20
*
      OutFmt = '('//char(N+ichar('0'))//'i5, ''  <--'', i5)'
      Lim = 1
      do 10 Idx = 2, N
         Lim = Lim * Idx
   10 continue
      print *, Lim, ' lines in all:'
      do 20 Idx = 0, Lim-1
         call GenPrm (Idx, N, Set)
         Tst = mod(Idx, 20)
	 print OutFmt, Set, Idx
         if (Tst .eq. 19) read '(a1)', TsT
   20 continue
      end
-- 
                                              --- Tim Rolfe
                                           rolfe@dsuvax.dsu.edu
                                            ROLFE@SDNET.BITNET
Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
From: R0264@vmcms.csuohio.edu
Subject: Re: Looking for random permutation generation algorithms
Organization: CSU
Date: Wed, 6 Jan 1993 21:57:58 GMT

In article <1993Jan6.014749.15323@ee.ubc.ca>
rayw@ee.ubc.ca (raymond w m woo) writes:
 
>
>Hi, does anyone know, or can provide any pointer in the literature to, any
>random permutation generation algorithm that can be easily implemented as a
>function in a computer program?
>
>Ideally, this function would be computationally effective, and the input
>that this function takes would be some kind of index/rank number of the
>permution to be generated.
>
>But of course, I am interested in knowing *all* kinds of permutation generation
>algorithms.
>
>Many thanks in advance!  Best of wishes for 93.
>--
> R Woo  <rayw@ee.ubc.ca> | When correctly interpreted, pi conveys the entire
> Elec. Eng., UBC, Canada | history of the human race!  --accord. to Dr. Matrix
  There are a couple of articles on such routines in Behavior Research Methods
  Instruments & Computers.  See  Castellan, N. J. (1992), Shuffling arrays:
  appearances may be deciving.  24,72-77.  The other one is cited there,
  and is by Brysbaert.
From: markh@csd4.csd.uwm.edu (Mark)
Newsgroups: comp.theory
Subject: Suggstion: (was: Re: P=NP; the proof)
Date: 7 Jan 1993 23:01:07 GMT
Organization: Computing Services Division, University of Wisconsin - Milwaukee
Distribution: inet
NNTP-Posting-Host: 129.89.7.4
Keywords: Collapse of hierarchy

In article <1ifljqINN137@nunki.anu.edu.au> jmr@cs.anu.edu.au (Mike Robson) writes:
>>So currently my proof is dead but if you believe in resurrection
>>watch this space.
>
>>Mike Robson.
>
>AARRGGHH!!
>
>Jim Reeds has proved that this problem cannot be fixed.

When you come up with a P=NP proof, first make sure you can translate it to
several of the other known NP-complete problems.  Each conversion should lead
to some significant result and insight if the original proof is correct.
Also, you'd get far more attention by simultaneously publicising polynomial
algorithms for 10 to 20 NP-complete problems, and a single tenuous and
highly abstract proof.  The conversions are in the literature, so it's
a trivial bookkeeping process to develop 20 algorithms from one.

Second, test the thing out before publicising it, by running the algorithms on
actual cases and then using these test cases to exemplify the algorithms when
you do publicise them.

If you're refereeing journals or otherwise trying to determine the validity
of P=NP proofs, reject all alleged proofs that don't meet the two criteria
above.
Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
From: lwloen@rchland.vnet.ibm.com (Larry Loen)
Subject: Re: Looking for random permutation generation algorithms
Date: Sat, 09 Jan 1993 22:09:21 GMT
Reply-To: lwloen@rchland.vnet.ibm.com
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
Organization: IBM Rochester


If I understand the request correctly, the original poster is looking
for a way of generating a pseudo random string of digits including all
number 0, 1. . . n-1 for n numbers, without repeating any.

The simplest way to do this comes from APL.  What you do is generate
a string of n numbers using any suitable random number generator.

Then, you do a "sort" of the numbers using the "index array" method.

That is, you leave the original numbers in place, and sort an array
of "indexes" to the original data.

As it happens, that sorted array will, itself, provide the array
required.  In other words, the original random numbers (that may have
had repeats) is discarded after the sort, because they were merely means
to an end.

Now, if that doesn't quite "cut" what is looked for, here, such an array
can probably be used to manipulate some sort of starting permutation
in a pseudo-random way with only a little more thought.  However, since
the numbers don't repeat, it would seem to form a permutation-substitution
by simply having index i replaced by index i+1 and so forth.

If one has a built-in sort handy, it is very easy to do.

-- 
   Larry W. Loen        |  My Opinions are decidedly my own, so please
                        |  do not attribute them to my employer
From: jos@and.nl (Jos Horsmeier)
Newsgroups: comp.theory
Subject: Re: Real Numbers vs. Rational Numbers?
Date: 4 Jan 93 11:30:46 GMT
Distribution: inet
Organization: AND Software BV Rotterdam

In article <1993Jan3.151347.29159@tom.rz.uni-passau.de> boerncke@kirk.fmi.uni-passau.de (Frank-Roland Boernke) writes:

||> Since "PI*PI" is a finite representation of PI * PI from which one can
||> algorithmically computer any of its digits in finite time, this counts as a
||> valid answer.
||> 
||> If you don't consider this valid, then neither will you consider this valid:
||> 
||> Calculate: 2 / 5
||> Answer: 2/5.
||> 
||> So then on that account, computers can't even work with fractions.

|I think there IS a difference:
|
|For 2/5 you can find a finite numeric representation ( 0.4 )
|for PI or PI*PI you cannot!

But what if we use a base PI representation? PI*PI obviously equals 100,
which is definitely a finite numeric representation. There is none for 2/5,
when using base PI.

kind regards and happy new year!

Jos aka jos@and.nl
From: mdm@math3.sma.usna.navy.mil (Mark D. Meyerson -- math  FACULTY <mdm@sma.usna.navy.mil>)
Newsgroups: comp.theory
Subject: Re: Looking for random permutation generation algorithms
Date: 8 Jan 93 15:20:59 GMT
Reply-To: mdm@math3.sma.usna.navy.mil (Mark D. Meyerson -- math  FACULTY <mdm@sma.usna.navy.mil>)

In reply to 22795: a permutation algorithm:

How about using an inductive (recursive) definition?
To get a permutation on  N  elements take a 
permutation on  N-1  elements and send the new  Nth
element to itself.  Then switch the  Nth  element 
with any of the  1..N  elements (including itself).
I would think this could be enumerated or randomized
as desired without much trouble.
From: jmr@cs.anu.edu.au (Mike Robson)
Newsgroups: comp.theory
Subject: Re: P=NP; the proof
Date: 7 Jan 1993 06:42:17 +1100
Organization: Computer Science Department, ANU, Australia
Distribution: inet
NNTP-Posting-Host: nunki.anu.edu.au
Keywords: Collapse of hierarchy

jmr@cs.anu.edu.au (Mike Robson) writes:


>Who can shoot down this alleged proof that P=NP?
>The ideas are taken from the Gismondi and Swart papers but the
>algorithms are simplified and the proofs are completely new.
>If you haven't read their papers, you will probably not follow this.
>I'll post a more detailed version soon unless anyone has convinced
>me I'm wrong (in which case I will post a retraction).

I was wrong about the dimensions of the matrix M since it has more
rows than the number of nonzero sab. I can't see any way to fix this
(though I am working on it). I've had mail from Peter Breuer of
Cambridge who says he has found a fix. I am looking forward to hearing
from him what it is.

So currently my proof is dead but if you believe in resurrection
watch this space.

Mike Robson.

Newsgroups: comp.theory
From: kaskubar@mayo.edu (Bruce Kaskubar)
Subject: Scheduling algorithms
Organization: Mayo Foundation, Rochester MN. Campus
Distribution: usa
Date: Tue, 5 Jan 93 15:52:16 GMT

Can anybody lead me to a body of literature regarding scheduling  
algorithms?

Thanks

Bruce Kaskubar, kaskubar@mayo.edu
Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
From: karr@cs.cornell.edu (David Karr)
Subject: Re: Looking for random permutation generation algorithms
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Date: Fri, 8 Jan 1993 16:39:09 GMT

Aaargh.  Somehow, in my effort to get the permutation algorithm
from my head to a clear written explanation, I managed to flub 
at least two key points.  Prof. Meyerson points out both of them:

In article <2607@usna.NAVY.MIL> mdm@math3.sma.usna.navy.mil (Mark D. Meyerson -- math  FACULTY <mdm@sma.usna.navy.mil>) writes:
>This method fails.  There is a minor error in that letting
>p=0 and using modular arithmetic gives zero values outside
>of the subscript range of the arrays.  This is easily 
>patched.

True.  I should have indexed both arrays v and w from 0 to N-1 in the
first place, and initialized t to N-1 as well.  I hope this fixes this
error.

>  But a major error is that  k mod b  won't 
>distinguish between different k.  The first example of this
>failure is for N=4 and k=4 or 16 (N!=24 so both k values occur.)

This is really the major omission from the algorithm.  I had meant
to compute both k mod b *and* k div b.  k mod b is used to index the
array for the current selection; k div b is then copied to k for the
next round.

With the division step properly included in the algorithm, the
resulting permutations for k=4 and k=16 are 1,4,3,2 and 1,2,4,3
respectively.  If you get different results then most likely I have
made some other error in the description of the algorithm.

Actually I suspect my algorithm may be fundamentally the same as
another one that was posted that was supposedly based on FORTRAN
multidimensional array indexing, but I came down with a bad case of
MEGO when I looked at the FORTRAN code so I can't say for sure.

-- David Karr (karr@cs.cornell.edu)



Xref: sparky comp.theory:2846 sci.crypt:6583 sci.math:17897 rec.puzzles:8302
From: marek@wigry.ucr.edu (marek chrobak)
Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
Subject: Re: Looking for random permutation generation algorithms
Date: 9 Jan 93 21:09:50 GMT
Followup-To: comp.theory
Organization: University of California, Riverside

In article <1993Jan8.210013.24614@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:

>As noted in Bentley's December 1987 column, an alternative to Floyd's
>algorithm is to initialize an array a[1..N] to a[i]=i and then scan
>along from a[1] to a[M], exchanging each such a[i] with a randomly
>selected a[j] for j >= i.
>
>For N = M (Woo's question) this method is the one Jim Roth gave.  It is
>preferable to Floyd's method because it does not entail testing for
>previous occurrences.
>
>But for N >> M it has two drawbacks: the time to initialize the array,
>and the space required for it, both being O(N).  In contrast Floyd's
>method requires space O(M) and time somewhere between O(M) and O(M^2)
>depending on the method used to test for repetitions.  (For N some
>modest multiple of M one might instead keep track of repetitions using
>an array of N bits, i.e. N/8 bytes, initialized to 0.)

This method also can be implemented in O(M) space and O(M logM) time.

The general idea is that there is no need to initialize and maintain
the whole array. Only M entries can be changed, so for other entries
A[i] = i. Use any balanced search tree for storing needed information.
For details see: Chrobak, Harter, A note on random sampling, Information
Processing Letters 29 (1988) 255-256.

Marek

-- 
------------------------------------------------------------------
Marek Chrobak                              email: marek@cs.ucr.edu
Department of Computer Science             phone: (714) 787-3769
University of California, Riverside        fax  : (714) 787-4643
Newsgroups: comp.theory
From: niek@ronnie.and.nl (Niek Yzinga)
Newsgroups: comp.theory
Subject: Technical Report/Addresses wanted
Date: 7 Jan 93 08:36:55 GMT
Organization: AND Software BV Rotterdam


I am very interested in the following technical report of the MIT
Operations Research Centre:

@techreport{AMOT88,
  AUTHOR = {R.K. Ahuja and K. Mehlhorn and J.B. Orlin and R.E. Tarjan},
  TITLE = {Faster algorithms on the shortest path problem},
  NUMBER = {193},
  YEAR = {1988},
  PUBLISHER = {MIT Operations Research Center}}

I would like to obtain a copy. 
An obvious way to do this is to contact the authors
of this report. I hope someone can supply me with one or more of
their email addresses or snailmail addresses.

Thank you very much for your help.

******************************************************
Niek IJzinga <niek@and.nl>

AND Software B.V.                   tel.+31-10-4367100
Westersingel 108                    fax +31-10-4367110
3015 LD Rotterdam
The Netherlands
******************************************************
From: plaisted@cs.unc.edu (David Plaisted)
Newsgroups: comp.theory
Subject: Gismondi and Swart's algorithm
Date: 7 Jan 1993 13:08:21 -0500
Organization: The University of North Carolina at Chapel Hill
Distribution: inet
NNTP-Posting-Host: plaisted.cs.unc.edu
Keywords: Graph isomorphism


Here is a possible counterexample to Gismondi and Swart's algorithm
for graph isomorphism.

We can think of the $s_{a,b}$ as relating the vertices a and b, giving
the degree to which a ``fuzzy isomorphism'' maps a to b.  We can think
of $t_{a,b,c,d} as relating the edge (a,b) of one graph to the edge
(c,d) of the other graph.  It's the degree to which a ``fuzzy
isomorphism'' maps (a,b) to (c,d).  Gismondi and Swart give an
associated linear programming problem in which a number of reasonable
linear inequalities are imposed on these values to try to characterize
isomorphism as closely as possible.

Let G1 be a graph consisting of two disjoint cycles of length n.  Let
G2 consist of one cycle of length 2n.  Then, the corresponding linear
programming problem of Gismondi and Swart is solvable with a solution
vector consisting entirely of 0 and .5 values.  Each vertex in G1
corresponds to two vertices in G2 by the fuzzy isomorphism.  Each
vertex in G2 corresponds to two vertices in G1 by this fuzzy
isomorphism.  The idea is that as you go around the long cycle in G2,
you go around each of the short cycles in G1, twice.  Also, it's not
possible to reduce any of the .5 coefficients to 0 without increasing
some 0 coefficient.  Of course, the graphs are not isomorphic.

Let H1 consist of disjoint copies of G1 and G2.  Let H2 be isomorphic
to H1.  Consider the linear programming problem corresponding to
showing that H1 is isomorphic to H2.  One possible solution to this is
the true isomorphism.  The other one is obtained by two copies of the
solution for G1 and G2 above.  So the G1 in H1 is related to the G2 in
H2 and the G2 in H1 is related to the G1 in H2.  Let's consider this
second solution.  All its values are 0 and .5.  Furthermore, it does
not cover a permutation, though one exists.  In addition, it is not
possible to reduce any of the .5 values to 0 without increasing some 0
value.

We can even make G1 and G2 and H1 and H2 connected, by adding a new
vertex connected to everything else.  Also, by extending this idea,
considerably more complicated counterexamples can be found.

I don't see any way that Gismondi and Swart's algorithm can
distinguish between these two cases, though I don't fully understand
their method.  So it seems to me that their approach is wrong and even
the algorithm is incorrect.  Of course, an implementation might happen
to give the right answer because of the solutions it happened to find.
So it seems that their approach cannot be saved except by some
fundamentally new ideas.

However, consider the set of pairs (G1, G2) of graphs such that the
associated linear programming problem has a (fractional) solution.
This seems to have a fairly restricted structure.  It also includes
the pairs of isomorphic graphs.  So maybe this linear programming
problem can be used as a preprocessing step for a graph isomorphism
algorithm.

	Dave Plaisted
From: pjones@MENTO.OIT.UNC.EDU (Paul Jones)
Newsgroups: comp.theory.dynamic-sys
Subject: Out of town (January 1 - 14)
Date: 6 Jan 93 20:23:28 GMT
Reply-To: Paul Jones <pjones@MENTO.OIT.UNC.EDU>
Distribution: inet
Organization: The Internet

Please excuse this rather impersonal message. I will be out of the office
from January 1 - 14. Your mail will be saved and answered once I
return.

For help with SunSITE and/or WAIS sources contact:
Simon Spero <simon_spero@unc.edu>
Jonathan Magid <Jonathan_magid@unc.edu>

For questions regarding the laUNChpad, aka bbs, aka ebb:
Dykki Settle <Dykki_Settle@unc.edu>

For help with the first_last@unc.edu ids:
Sherry Graham <sherry_graham@unc.edu>

For help with DNS aka nameservers aka host registration contact:
Jim Gogan <jim_gogan@unc.edu>

For other pressing problems please contact:
Judd Knott <knott@unc.edu>

This version of the vacation program makes several attempts to see if our
message originated from a mailing list, if so it should not respond.
Further, I had sent NOMAIL or unsubscribed to all of the lists that I can
remember that I've ever subscribed to. If you subscribed to a list and get
this message I appologize. If you manage a list and get this message,
please consider making your list conform to some network standards for
lists.  No message will be sent if the initial ``From'' line includes the
string ``-REQUEST@'' or if a ``Precedence: bulk'' or ``Precedence: junk''
line is included in the header.

Thanks for your patience,
Paul Jones
From: G_GOODWIN@TWU.BITNET
Newsgroups: comp.theory.dynamic-sys
Subject: RE: Your subscription to list DYNSYS-L
Date: 13 Jan 93 01:50:00 GMT
Reply-To: G_GOODWIN%TWU.BITNET@cmsa.Berkeley.EDU
Distribution: inet
Organization: The Internet

ACK
From: hurd@MATH.GATECH.EDU (Lyman Hurd)
Newsgroups: comp.theory.dynamic-sys
Subject: new book: Fractal Image Compression
Date: 6 Jan 93 18:48:04 GMT
Reply-To: Lyman Hurd <hurd@MATH.GATECH.EDU>
Distribution: inet
Organization: The Internet

I am pleased to announce the arrival of the book:

Fractal Image Compression
by Michael Barnsley and Lyman Hurd.

hardbound 244 pages, 16 color plates


A sequel to Fractals Everywhere, Fractal Image Compression describes the
mathematics underlying the Fractal Transform an image compression method
discovered by Michael Barnsley and developed at Iterated Systems.  Topics
include:

  * Iterated Function Systems

  * Local IFS and the Black and White Fractal Transform

  * The Grayscale Fractal Transform

  * Information Theory

  * Huffman codes

  * Arithmetic Codes

  * JPEG Image Compression

Example programs in C are interspersed throughout the text.

Copies can be ordered directly from the publisher by the  following
methods:

1) Email: send a message to kpeters@math.harvard.edu with name address and
a Mastercard or Visa card number WITH EXPIRATION DATE.

2) Mail: Check or money order or the above credit card information to:

AK Peters, Ltd.
289 Linden St.
Wellesley, MA 02181

3) Phone (credit card orders) (617) 235-2210 (voice) (617) 235-2404 (fax)

The book is $49.95 including shipping.  Residents of Massachusetts please
add 5% sales tax.