MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Algorithm Questions

  • To: mathgroup at smc.vnet.net
  • Subject: [mg29400] Re: [mg29386] Algorithm Questions
  • From: BobHanlon at aol.com
  • Date: Sat, 16 Jun 2001 22:43:49 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com

In a message dated 2001/6/16 2:58:57 AM, huzhe at public3.sta.net.cn writes:

>I am wondering that if Mathematica has lazy-evaluation features. Say I
>
>am going to extract 100 lists from the permutation lists of {1, 
>2,...,100} (Permutation[Range[100]]) randomly.
>
>If I program like this:
>
>largeList = Permutation[Range[100]];
>
>indx = Table[Random[Integer, {1, 100!}], {100}];
>
>Part[largeList, indx]
>
>the program is very slow, since it works out all the 100! elements for
>
>the largeList, while I only need 100 items from it.
>
>Can I program like this ? Say,
>
>take 100 (somePermutationFunction 100)
>
>so that the permutation stops after 100 lists were taken. (I learned 
>that it's called lazy-evaluation from Haskell.)
>
>The second question is that:
>
>I want the 100 lists randomly taken to be all different.
>
>So I program this way:
>
> While[Length[a] != 100,
>      a = (Table[Random[Integer, {1, n!}], {100}] // Union)];
>
>there must be more efficient solutions, especially to combine the 
>solution with the first question?
>
>
>So my slow program is like this, deeply welcome suggestions to improve
>
>it:
>
>randomList[n_, k_] :=
>  Module[{a},
>    While[Length[a] != k,
>      a = (Table[Random[Integer, {1, n!}], {k}] // Union)];
>    Part[Permutations[Range[n]], a]]
>

Needs["DiscreteMath`Combinatorica`"];

randomList[n_Integer?Positive, k_Integer?Positive] := 
    Module[{a = Union[Table[RandomPermutation[n], {k}]]}, 
      While[Length[a] < k, 
        a = Union[Append[a, RandomPermutation[n]]]];
      a];

Timing[Length[Union[randomList[100, 100]]]]

{0.6999999999998181*Second, 100}


Bob Hanlon
Chantilly, VA  USA


  • Prev by Date: Re: roots
  • Next by Date: Re: Algorithm Questions
  • Previous by thread: Algorithm Questions
  • Next by thread: Re: Algorithm Questions