From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <zsh-workers-return-44974-ml=inbox.vuxu.org@zsh.org>
X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on inbox.vuxu.org
X-Spam-Level: 
X-Spam-Status: No, score=-1.0 required=5.0 tests=DKIM_ADSP_CUSTOM_MED,
	FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_NONE autolearn=ham
	autolearn_force=no version=3.4.2
Received: from primenet.com.au (ns1.primenet.com.au [203.24.36.2])
	by inbox.vuxu.org (OpenSMTPD) with ESMTP id 757b7b34
	for <ml@inbox.vuxu.org>;
	Mon, 2 Dec 2019 15:28:39 +0000 (UTC)
Received: (qmail 6820 invoked by alias); 2 Dec 2019 15:28:34 -0000
Mailing-List: contact zsh-workers-help@zsh.org; run by ezmlm
Precedence: bulk
X-No-Archive: yes
List-Id: Zsh Workers List <zsh-workers.zsh.org>
List-Post: <mailto:zsh-workers@zsh.org>
List-Help: <mailto:zsh-workers-help@zsh.org>
List-Unsubscribe: <mailto:zsh-workers-unsubscribe@zsh.org>
X-Seq: 44974
Received: (qmail 12888 invoked by uid 1010); 2 Dec 2019 15:28:34 -0000
X-Qmail-Scanner-Diagnostics: from mail-il1-f182.google.com by f.primenet.com.au (envelope-from <roman.perepelitsa@gmail.com>, uid 7791) with qmail-scanner-2.11 
 (clamdscan: 0.102.0/25649. spamassassin: 3.4.2.  
 Clear:RC:0(209.85.166.182):SA:0(-2.0/5.0):. 
 Processed in 1.011567 secs); 02 Dec 2019 15:28:34 -0000
X-Envelope-From: roman.perepelitsa@gmail.com
X-Qmail-Scanner-Mime-Attachments: |
X-Qmail-Scanner-Zip-Files: |
Received-SPF: pass (ns1.primenet.com.au: SPF record at _netblocks.google.com designates 209.85.166.182 as permitted sender)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20161025;
        h=x-gm-message-state:mime-version:references:in-reply-to:from:date
         :message-id:subject:to:cc;
        bh=yHDDpP3Lx8xJTERAzUHHdzs7Ezpo4K0j+ULyrDWMekI=;
        b=F22y/bG4jVWDYjxd9zxILzWaWE1ivr8FjzrPqdpiJiLvj86dlqVL+uaQKGhFL+1p1g
         pDirW+HDL5lW9Zxc05ss1iR1JCFP3svmVkKBMiRwX4sJ+1qZhD5ZCKQ4uH1+QrGgt8Tb
         KYuPyYK741y/F45+XcaRR8uWwEx2qgRoHh5JYjxOgSvq1l5pb7gy8Z+jAEM6dpiRwKRk
         wU+9geIItCZ7YhChMAHFjXPrc2HVtAB59ic8QqmU91tzGYr+sZJm49HpRSxZPZ/e8Ds8
         ZQrCfRwclASVeOp0r42J1lLJ27/AWawe5auT2V2Vg0JVNIbLhtE+yUC1cfzu58DC/PUj
         UzQQ==
X-Gm-Message-State: APjAAAV+LOYgEskwfE3/9Hf8ym3yNgJ2s0ptdkod+VsijI2uAdo4KwAs
	Qd8xiTy49/YsBYLD4B1D2z6lT8A6q+xBO3Z1FS0=
X-Google-Smtp-Source: APXvYqzqkpB6cVDMn03BuVyjDsCo6LeG/je6SPbxkHnD9p5Z7/59M5V8c+oW/lv5HClHND6rrl34zGWQC4o5lG21GQ4=
X-Received: by 2002:a92:290a:: with SMTP id l10mr20539924ilg.151.1575300479562;
 Mon, 02 Dec 2019 07:27:59 -0800 (PST)
MIME-Version: 1.0
References: <867e3jxtao.fsf@zoho.eu> <20191129064215.GA14095@prometheus.u-strasbg.fr>
 <8636e7w0w9.fsf__36104.0529723809$1575015640$gmane$org@zoho.eu>
 <20191201200719.anzbs27c7phgdnmm@chaz.gmail.com> <20191201233848.7selcpkvenlu65px__33142.5388505281$1575243619$gmane$org@tarpaulin.shahaf.local2>
 <20191202141421.sj7nlhsdrpqxpr42@chaz.gmail.com> <CAN=4vMpt+hQw2zxUC1LH+3bPymBX_5qqexFw-vqkN6ye+dG1ZQ__45487.0572009654$1575297047$gmane$org@mail.gmail.com>
 <20191202151652.yke22w7mign4i26q@chaz.gmail.com>
In-Reply-To: <20191202151652.yke22w7mign4i26q@chaz.gmail.com>
From: Roman Perepelitsa <roman.perepelitsa@gmail.com>
Date: Mon, 2 Dec 2019 16:27:48 +0100
Message-ID: <CAN=4vMqN4b2MyCvLXMBWQ_bvaRSY7SSiaGSPRT0bm5z4k3g7Vg@mail.gmail.com>
Subject: Re: shuffle array
To: Stephane Chazelas <stephane.chazelas@gmail.com>
Cc: Zsh hackers list <zsh-workers@zsh.org>
Content-Type: text/plain; charset="UTF-8"

On Mon, Dec 2, 2019 at 4:21 PM Stephane Chazelas
<stephane.chazelas@gmail.com> wrote:
> shouldn't that be "RANDOM % $#l + 1"?

No, the original code is correct. There is a loop invariant that
l[1,i-1] is shuffled before each iteration. An iteration makes l[1,i]
shuffled.

It's fairly easy to prove that this algorithm will produce each array
permutation with equal probability (assuming that we have access to a
function that gives a random number from [1, N] with uniform
distribution.)

> Or use rand48() in zsh/mathfunc

Thanks, TIL.

Roman.