From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <zsh-users-return-24491-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 362c8678
	for <ml@inbox.vuxu.org>;
	Mon, 2 Dec 2019 14:30:09 +0000 (UTC)
Received: (qmail 920 invoked by alias); 2 Dec 2019 14:30:02 -0000
Mailing-List: contact zsh-users-help@zsh.org; run by ezmlm
Precedence: bulk
X-No-Archive: yes
List-Id: Zsh Users List <zsh-users.zsh.org>
List-Post: <mailto:zsh-users@zsh.org>
List-Help: <mailto:zsh-users-help@zsh.org>
List-Unsubscribe: <mailto:zsh-users-unsubscribe@zsh.org>
X-Seq: 24491
Received: (qmail 20688 invoked by uid 1010); 2 Dec 2019 14:30:02 -0000
X-Qmail-Scanner-Diagnostics: from mail-io1-f54.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.54):SA:0(-2.0/5.0):. 
 Processed in 0.691269 secs); 02 Dec 2019 14:30:02 -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.54 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;
        bh=FOEEK3Rt9YcbdHFczlbQP1mB3vZ/qv84IyLtLFaXGvI=;
        b=ElIcJX7m2DY0lBSJah7xRNnF2QB9fSYKQfvBczTg4NhIES8Gb83JLdWL8y/lGT+CZA
         PeSSGkuTVWswUzBVGJnVCbKqndIZw1H3ji6dO7bdgp1PVo7YpKeQAWifecCg93lQQ8ip
         cxQ/KEl3G/yNt9jbwxu56K3jwtn5H2XMWjKVhH0s3yq9Gz+ySM2osTnLTYwR+pwMHIj7
         cIVu7/4VDlAmIugmwSPeFZ7WnfzVh/UE4K99cdpltsYaIxcREHq4kU6Zqwll428LfNcN
         u8Pz3wprikb58H7GPGFhow2AEQcqS0ivDmJBuqbPiGBMHXqEnie643IMjmyu148Q96qY
         kA1w==
X-Gm-Message-State: APjAAAWZVJ/WZCF30naeX+nFDbgR0JKXb86ckW3j5Z075Ijj9WypjW4Z
	31T9ZQwBu/U+TRZgr45fIOAy07zF93QaUB177sGZaTAI
X-Google-Smtp-Source: APXvYqxSK6Ysp6nufWctfAZhS378fP9MDw9RTl4pV4qzswzkj9bpWH8qHTrp4UVDniFanKU073a3/zlNN82ECvaVWuo=
X-Received: by 2002:a6b:760c:: with SMTP id g12mr53695169iom.304.1575296968922;
 Mon, 02 Dec 2019 06:29:28 -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>
In-Reply-To: <20191202141421.sj7nlhsdrpqxpr42@chaz.gmail.com>
From: Roman Perepelitsa <roman.perepelitsa@gmail.com>
Date: Mon, 2 Dec 2019 15:29:17 +0100
Message-ID: <CAN=4vMpt+hQw2zxUC1LH+3bPymBX_5qqexFw-vqkN6ye+dG1ZQ@mail.gmail.com>
Subject: Re: shuffle array
To: Daniel Shahaf <d.s@daniel.shahaf.name>, Zsh Users <zsh-users@zsh.org>
Content-Type: text/plain; charset="UTF-8"

Another alternative is to implement the standard inplace shuffle
algorithm from scratch:

    local -i i
    for ((i = 2; i <= $#l; ++i)); do
      local j=$((RANDOM % i + 1))
      # swap l[i] and l[j]
      local tmp=$l[i]
      l[i]=$l[j]
      l[j]=$tmp
    done

Due to RANDOM having a rather narrow range, this will introduce bias
on large arrays and won't work at all on arrays with more than 32k
elements. These issues can be mitigated by replacing RANDOM with
(RANDOM << 15 | RANDOM) or even with (RANDOM << 30 | RANDOM << 15 |
RANDOM).

Roman.