robison@m.cs.uiuc.edu (08/17/88)
Though the following appears to be a math problem, I'm posting in comp.lang.misc
because the problem was stated in the context of imperative languages vs.
applicative languages. [1] says that the fastest imperative algorithm takes
O(n) time, while the fastest applicative algorithm takes O(n log n) time.
Problem: Random Permutation
Description: Given n and a sequence of n integers drawn independently
from a uniform distribution over 1..n, produce a uniformly
random permutation of the sequence 1..n.
My question is: Am I either misreading the question? It would seem to
be impossible. There are n^n possible inputs, and n! possible outputs.
In general n! does not divide n^n evenly. Can anyone clarify this, or
put me in contact with the authors?
[1] Carl G. Ponder, Patrick C. McGeer, and Antony P-C. Ng,
"Are applicative languages inefficient?", SIGPLAN Notices,
vol. 23,6, June 1988, 135-139.
Arch D. Robison
University of Illinois at Urbana-Champaign
CSNET: robison@UIUC.CSNET
UUCP: {pur-ee,convex}!uiucdcs!robison
ARPA: robison@CS.UIUC.EDU (robison@UIUC.ARPA)g-rh@cca.CCA.COM (Richard Harter) (08/17/88)
In article <5200012@m.cs.uiuc.edu> robison@m.cs.uiuc.edu writes: >Though the following appears to be a math problem, I'm posting in comp.lang.misc >because the problem was stated in the context of imperative languages vs. >applicative languages. [1] says that the fastest imperative algorithm takes >O(n) time, while the fastest applicative algorithm takes O(n log n) time. > Problem: Random Permutation > Description: Given n and a sequence of n integers drawn independently > from a uniform distribution over 1..n, produce a uniformly > random permutation of the sequence 1..n. >My question is: Am I either misreading the question? It would seem to >be impossible. There are n^n possible inputs, and n! possible outputs. >In general n! does not divide n^n evenly. Can anyone clarify this, or >put me in contact with the authors? You are misreading the question. There is only one input, namely the given sequence of length n. The problem is that you are given a sequence of integers a1 ... an. Generate a uniformly random permutation of that sequence. From the statement of the problem there may be duplicates in the sequence, but that is irrelevant. The imperative algorithm runs as follows: for i from [1...n] sequentially chosen select j from [i...n] randomly exchange a(i),a(j) end loop --- -- In the fields of Hell where the grass grows high Are the graves of dreams allowed to die. Richard Harter, SMDS Inc.
ken@aiva.ed.ac.uk (Ken Johnson) (08/19/88)
Story so far: Looking for a way of randomly permuting N elements in a declarative language. The imperative algorithm is > for i from [1...n] sequentially chosen > select j from [i...n] randomly > exchange a(i),a(j) > end loop Here it is in Prolog. Untested etc. I am reasonably certain you could speed this up, but the question was to show that it could be done at all, and I've only got ten minutes... % randperm(List_in,List_out) % Random permutation of List_in. Mode: randperm(+,-). % Not debugged, warranted or anything. If you copy this source in a % program and make money out of it, please send me some. % Good Luck! randperm(List_in,List_out) :- length(List_in,N), % Length of list (system func) randperm(1,N,List_in,List_out). randperm(I,N,List_in,List_in) :- % Done I > N. randperm(I,N,List_in,List_out) :- I =< N, random(N,R), % Library function (?) R is random int % between 1 and N inclusive exchange_elements(I,R,List_in,List_1), % Swap elements J is I + 1, randperm(J,N,List_1,List_out). exchange_elements(I,J,List_in,List_out) :- % Get Ith and Jth elements get_elem(I,List_in,Ei), % and swap. This is more get_elem(J,List_in,Ej), % time consuming than put_elem(J,List_in,Ei,List_1), % necessary but it will work put_elem(I,List_in,Ej,List_out). get_elem(1,[X|_],X). % Find I'th element of list get_elem(I,[_|T],X) :- I > 1, I1 is I - 1, get_elem(I1,T,X). put_elem(1,[_|T],X,[X|T]). % Replace I'th element of % list by X giving new list put_elem(I,[H|T],X,[H|U]) :- I > 1, I1 is I - 1, put_elem(I1,T,X,U). -- ------------------------------------------------------------------------------ From: Ken Johnson (Half Man Half Bicycle) Address: AI Applications Institute, The University, EDINBURGH Phone: 031-225 4464 ext 212 Email: k.johnson@ed.ac.uk
wsmith@m.cs.uiuc.edu (08/22/88)
This is an example of why informal specifications are not always the
best. If the problem that was meant to be described and the problem
that was described in responses to this discussion are put next to each other,
they don't match. The specification says that the random integers are drawn
from 1 to n, while the implementation draws the integers from [i..n].
^ ^
These are not the same thing.
#
# Problem: Random Permutation
#
# Description: Given n and a sequence of n integers drawn independently
# from a uniform distribution over 1..n, produce a uniformly
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
# random permutation of the sequence 1..n.
> for i from [1...n] sequentially chosen
> select j from [i...n] randomly
^^^^^^^
> exchange a(i),a(j)
> end loop
I would vote that the informal specification does not specify the intended
problem. I propose that instead of selecting n integers drawn from
1..n, the problem specifiction only require that the product of the ranges of
the selected numbers equal n!. I think that, if it were correct, the original
specification is biased to the imperative language's implementation.
Proposed problem definition:
< Description: Given n and a sequence of integers selected from a
< uniform distribution of 1 to m[i] for the ith integer,
< subject to the constraint that the product of the m[i]'s
< equals n!, produce a uniformly random permutation of the
< sequence 1..n.
The problem requires the numbers being shuffled to be the numbers 1 to n
and that the amount of "randomness" used to be a minimum.
Bill Smith wsmith@cs.uiuc.edu uiucdcs!wsmithrobison@m.cs.uiuc.edu (08/23/88)
The paper cited[1] deliberately specifies problems biased towards imperative
languages. The authors are asking if applicative languages are inherently
slower than imperative languages (in the asymptotic sense). Seven problems
were specified for which the known imperative solutions are faster than
the known applicative solutions. For example, another problem in the paper is:
Problem: Array Transactions
Description: Given n and sequence of k read/write operations to array
indexed 1,...,n, produce the sequence of results of the
read operations. Let k>n.
This is solvable in O(k) time on an imperative machine, but the best known
on an applicative machine is O(k log n). (The solution simulates the array
with an AVL tree.)
[1] Carl G. Ponder, Patrick C. McGeer, and Antony P-C. Ng,
"Are applicative languages inefficient?", SIGPLAN Notices,
vol. 23,6, June 1988, 135-139.
Arch D. Robison
University of Illinois at Urbana-Champaign
CSNET: robison@UIUC.CSNET
UUCP: {pur-ee,convex}!uiucdcs!robison
ARPA: robison@CS.UIUC.EDU (robison@UIUC.ARPA)ok@quintus.uucp (Richard A. O'Keefe) (08/23/88)
In article <532@aiva.ed.ac.uk> ken@uk.ac.ed.aiva (Ken Johnson,E32 SB x212E) writes: >Story so far: Looking for a way of randomly permuting N elements >in a declarative language. >Here it is in Prolog. Untested etc. I am reasonably certain you could >speed this up, but the question was to show that it could be done at all, >and I've only got ten minutes... This topic has already been discussed in comp.lang.prolog. Results to date: if terms can have at most K elements, an O(N.log N) worst case time method exists. K if terms can have any number of elements (say >2N), an O(N) expected time method exists. An O(N.lg N) method is available in the Quintus Prolog library. It has the structure of a sort, but instead of doing comparisons it generates O(N.lg N) random bits. [An N.log(K,N) method would be like a radix sort.] Note that since there are N! permutations, a method of generating random permutations must generate at least lg(N!) = O(N.lg N) random bits.