重複無し乱数 DouKaku?

整数nを渡すと1 ～ n までの整数を重複しないようランダムに出力する関数「bingo」を作ってください。

このお題はraynstardさんの投稿を元にしています。ご投稿ありがとうございました。投稿の内容には表示のしかたも含まれていたのですが、このお題では「重複しない1～nまでの乱数をどうやって作るか」という点に集中することにして、結果の整形は続編としてこの後のお題で出すことにします。サンプル入出力は下のようになります。

>>> bingo(10)
[10, 7, 8, 4, 5, 2, 3, 1, 6, 9]
>>> bingo(3)
[2, 3, 1]
>>> bingo(3)
[2, 3, 1]
>>> bingo(3)
[3, 1, 2]
>>> bingo(10)
[7, 3, 8, 6, 4, 10, 9, 2, 1, 5]

Squeak Smalltalk で。

1
2
3

| bingo |
bingo := [:n | (1 to: n) asArray shuffled].
bingo value: 10   "=> #(6 9 3 4 2 1 10 5 8 7) "

using System;
using System.Text;
class Program
{
  static void Main()
  {
    Console.WriteLine(bingo(3));
  }
  static string bingo(int n)
  {
    Random r = new Random();
    int[] a = new int[n];
    for (int i = 0; i < n; ++i) a[i] = i + 1;
    for (int i = n; i > 1; --i)
    {
      int k = r.Next(i);
      int tmp = a[i - 1];
      a[i - 1] = a[k];
      a[k] = tmp;
    }
    StringBuilder sb = new StringBuilder("(");
    for (int i = 0; i < n; ++i)
    {
      if (i > 0) sb.Append(", ");
      sb.Append(a[i]);
    }
    sb.Append(")");
    return sb.ToString();
  }
}

Pythonでも1～nのリストを作ってシャッフルする方法が一番てっとりばやいですね。

>>> bingo(10)
[10, 8, 2, 7, 4, 5, 3, 6, 1, 9]

def bingo(n):
	from random import shuffle
	result = range(1, n + 1)
	shuffle(result)
	return result

久々の1行問題

def bingo(n)
  (1..n).to_a.sort_by{rand}
end
bingo 10                        # => [4, 2, 1, 10, 8, 5, 3, 7, 6, 9]
bingo 3                         # => [3, 1, 2]
bingo 3                         # => [1, 3, 2]
bingo 3                         # => [2, 3, 1]
bingo 10                        # => [3, 2, 6, 5, 7, 4, 1, 8, 10, 9]

1 2	use List::Util qw/shuffle/; sub bingo {shuffle(1..$_[0]);}

Number bingo := method(
    Range
    1 to(self) asList shuffle
}

10 bingo println

普通にやってみた

def bingo(num)
        raise ArgumentError.new("fixnum only") unless num.kind_of? Fixnum
        raise ArgumentError.new("1 ijyou de onegai simasu") unless num >= 1

        results = []

        ary=(1..num).to_a
        ary.size.times{
                index = (rand * ary.size).to_i
                results << ary.delete_at(index)
        }

        results
end

巧みだなあと思ったんですが、ごくわずかの確率でrandが同じ値を返すケースがあるはずで、その場合の要素の並び順はsortの実装によって固定されてしまうから、微妙に偏りが出てくるんじゃないかな、という気もします。

(例えば簡略化のために要素数を2つ、randは0か1しか返さないとして、sortがstableだとすると、可能な4通りの組み合わせのうち(0 1)が3回、(1 0)が1回となる)

現実にはdoubleが重なる確率なんて極めて低いでしょうけど。

ランダムソートでいいのかな

#include <stdio.h>
#include <stdlib.h>

static int cmp(const void *p1, const void *p2)
{
    return (rand() % 2)?1:-1;
}

void bingo(int num)
{
    int i;
    int *nums;

    if(num <= 0) return;
    nums = (int*)malloc(sizeof(int) * num);
    for(i=0; i<num; i++){
        nums[i] = i + 1;
    }
    qsort(nums, num, sizeof(int), (int (*)(const void*, const void*))cmp);
    for(i=0; i<num; i++){
        printf("%d\n", nums[i]);
    }
    free(nums);
}

int main(int argc, char *argv[])
{
    if(argc < 2){
        return EXIT_FAILURE;
    }
    srand(time(NULL));
    bingo(atoi(argv[1]));
    return EXIT_SUCCESS;
}

ライブラリを使ってシャッフルしているケースでももしかするとそういう偏りがある可能性はありますね。

気になったのでPythonのrandomライブラリを見てみたところ#2254と同じアルゴリズムでした。

for i in reversed(xrange(1, len(x))):
    # pick an element in x[:i+1] with which to exchange x[i]
    j = int(random() * (i+1))
    x[i], x[j] = x[j], x[i]

% awk -f bingo.awk
5
[3, 5, 1, 4, 2]
24
[22, 11, 5, 2, 4, 3, 9, 24, 6, 7, 17, 16, 21, 15, 19, 18, 12, 14, 13, 23, 10, 20, 8, 1]
10
[7, 4, 9, 3, 5, 10, 2, 1, 8, 6]
10
[10, 8, 3, 2, 6, 7, 1, 9, 5, 4]
10
[5, 7, 1, 8, 10, 3, 6, 2, 4, 9]
10
[6, 2, 3, 5, 1, 9, 8, 10, 7, 4]
10
[6, 9, 8, 5, 4, 2, 1, 3, 10, 7]

BEGIN {
	srand
}

{
	n = $1

	bingo(n,ar)
	show(n,ar)
}

function show(n,ar, i)
{
	printf "["
	for (i=1; i<n; i++) printf("%d, ", ar[i])
	printf("%d]\n", ar[n])
}

function rand_between_1_and_n(n, x)
{
	x = 1 + int(rand * n)
	return (x <= n)? x : rand_between_1_and_n(n)
}

function bingo(n,ar,  i,x,y,t)
{
	delete ar
	for (i=1; i<=n; i++) ar[i] = i

	for (i=n*2; i>0; i--) {
		x = rand_between_1_and_n(n)
		y = rand_between_1_and_n(n)
		if (x == y) continue

		t = ar[x] ; ar[x] = ar[y] ; ar[y] = t
	}
}

rand() % 2 ではだめでしょう。

see: http://www001.upp.so-net.ne.jp/isaku/rand.html

Cleanでやってみた。
擬似乱数を生成するライブラリをつかってます。
本当の乱数じゃないので、同じ数を与えると同じ乱数表になってしまう…

see:

module RandList
import StdEnv, MersenneTwister

Start = bingo 10
bingo n  = map snd  (sort  (zip ((genRandInt n),[1..n])))

System.Random を使う。シャッフルをナイーブに実装したもの

module Main (main) where

import System.Environment
import System.Random

shuffle :: [a] -> StdGen -> Int -> [a] -> [a]
shuffle acc _ 0 _  = acc
shuffle acc g n xs = case randomR (0,n-1) g of
 (i,g') -> case splitAt i xs of
             (ys,z:zs) -> shuffle (z:acc) g' (n-1) (ys++zs)

main :: IO ()
main = do { x:_ <- getArgs
          ; g0  <- getStdGen
          ; let n = read x
          ; putStrLn $ show $ shuffle [] g0 n [1..n]
          }

{-
% ./bingo 10
[4,10,3,2,9,5,7,8,6,1]
% ./bingo 10
[2,7,6,8,4,1,9,5,3,10]
% ./bingo 10
[1,7,3,10,6,4,8,2,5,9]
% ./bingo 10
[6,8,9,3,10,4,1,5,2,7]
-}

1 2	import scala.util.Sorting.stableSort def bingo(n:int) = stableSort[int,double](1 to n,{x=>Math.random})

破壊的シャッフル。

Array.prototype.$huffle = function(){
  for(var $, r, i = this.length; i;)
    $ = this[r = Math.random() * i-- | 0], this[r] = this[i], this[i] = $;
  return this;
}
function bingo(n){
  for(var a = []; n > 0;) a[a.length] = n--;
  return a.$huffle();
}

C言語と再帰で解いて見た。
ソート関数は利用していません。多分線形時間。

**intを与えているのがちょっとかっこ悪いですが。
あと↓の部分をまともになるように書き換えればOKだけど、アルゴリズムの本質ではないので放置。
swap_point = rand() % (num+1);

アルゴリズムは以下のような感じ
[1～n-1までがシャッフルされた配列] [n]
↑のような配列があったときに、
末尾要素と、ランダムで選ばれた末尾より前の要素とスワップすることで、
全体が1～nまでがシャッフルされた配列になります。
あとはそいつを再帰している感じ。
ループで書いてもよかったかな。

#include <stdio.h>
#include <stdlib.h>

void _bingo(int num, int *result, int num_max){
	int temp;
	int swap_point;

	result[num] = num + 1;
	swap_point = rand() % (num+1);
	temp = result[swap_point];
	result[swap_point] = result[num];
	result[num] = temp;

	if (num + 1 == num_max){
		return;
	}
	_bingo(num+1, result, num_max);
	return;
}

void bingo(int num, int** result)
{
	*result = (int*)malloc(num * sizeof(int));
	_bingo(0, *result,num);
}


int main(void)
{
	int *result;
	int num;
	int i;

	num = 100;
	bingo(num, &result);
	
	for(i = 0; i < num; i++){
		printf("%d,", result[i]);
	}
}

あ、freeしてねぇ orz...
mainの最後の行に free(result) を追加してください。

投稿してから気づきましたが、#2254やpythonのshuffleアルゴリズムと同じですね。

#light
let shuffle ls =
    let rnd = new System.Random() in
    List.sort (fun x y-> rnd.Next(-1,2)) ls;;

let bingo n = shuffle [1..n]

1～nまでのリストをRangeで生成して，
RandomSampleでシャッフルしました．

実行例：
In[2]:= bingo[10]
Out[2]= {6, 3, 10, 8, 1, 2, 9, 5, 4, 7}

RandomSampleで再利用無しの要素取得，
RandomChoiceで再利用OKの要素取得が
できるようになってます．

see: Mathematica - RandomSample

1	bingo[n_] := RandomSample[Range[n]];

AddしてRemoveAt。

Public Sub bingo(ByVal n As Integer)
    Dim list As New List(Of Integer)
    For i As Integer = 1 To n
        list.Add(i)
    Next
    Dim r As New Random
    For i As Integer = 1 To n
        Dim index As Integer = r.Next(0, n)
        list.Add(list(index))
        list.RemoveAt(index)
    Next

    For Each i As Integer In list
        Console.Write(i.ToString & ", ")
    Next
End Sub

std::random_shuffle を使います。乱数生成関数オブジェクトを指定しないと、何度実行しても同じ乱数列を発生させてしまうので、srand()を使う関数オブジェクトを定義します。

普通はtime()で得られる値を種にするらしいのですが、これは秒単位なので、同一秒内で再度実行すると、やはり同じ乱数列が得られてしまい、うまくありません。

そこで、Windowsでは、起動からのミリ秒を種として渡すことにしました。

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstdlib>

#ifdef _WIN32
# include <windows.h>
# define seed() ::GetCurrentTime()
#else
# include <ctime>
# define seed() std::time(NULL)
#endif

struct RandomGenerator
{
    RandomGenerator()
    {
        std::srand(static_cast<unsigned>(seed()));
    }

    int operator()(int n) const
    {
        return std::rand() % n;
    }
};

void bingo(size_t n)
{
    std::vector<size_t> v;

    for (size_t i = 0; i < n; ++i)
    {
        v.push_back(i);
    }

    static RandomGenerator gen;

    std::random_shuffle(v.begin(), v.end(), gen);

    std::copy(v.begin(), v.end(), std::ostream_iterator<size_t>(std::cout, " "));

    std::cout << std::endl;
}

int main()
{
    bingo(10);
    bingo(3);
    bingo(3);
    bingo(3);
    bingo(10);
}

標準のrandpermという関数が問のbingoと全く同じ動作をします。投稿のコードはsortがソート前の順序を返すことを使った別解です。

1 2	function r = bingo(n) [m r] = sort(rand(1,n));

参考になりました、あと stdlib.h の qsort() を使い回したのも良くないですね。
皆さんのより良いシャッフル方法を参考にさせて頂こうと思います。

#2269 によると rand() % n はまずいということなので、修正しました。std::min や std::max は [0, n) の範囲にあることを保証するため、念のため。

--- main.orig	Sat Aug 18 00:35:58 2007
+++ main.cpp	Sat Aug 18 00:41:24 2007
@@ -21,7 +21,9 @@ struct RandomGenerator
 
     int operator()(int n) const
     {
-        return std::rand() % n;
+        const int i = static_cast<int>(static_cast<double>(std::rand()) * n / RAND_MAX);
+
+        return std::max(0, std::min(i, n - 1));
     }
 };

(print (bingo 10))
 => (2 4 8 10 6 7 5 9 3 1)

(defun bingo (n)
  (loop repeat n
        for rand = (loop 
                     (let* ((*random-state* (make-random-state t))
                            (rand (1+ (random n))))
                       (if (not (member rand lst))
                         (return rand))))
        collect rand into lst
        finally (return lst)))

Rもそうですが、MathematicaやMATLABのような数値解析系はこういうの簡単に書けますね。
元のお題は「n * nのビンゴを出力せよ」みたいな感じだったのかな。

> sample(10)
 [1]  1  9  4 10  3  5  7  2  8  6

1	bingo <- sample

標準で必要な関数があるのにあえて別解を用いるメリットが最初の例では特に無かったので、少し書き換えてk個の列を一度に返せるようにした。標準のrandpermでk個生成するにはループでk回呼ばないといけない。余談だがMATLAB7.4ではデフォルトの乱数生成アルゴリズムとして#2269さんのリンク先でも紹介されているメルセンヌ・ツイスタが採用されている。

function r = bingo(n,k)
% r = bingo(n) retruns a random permutation of 1:n.
% r = bingo(n,k) returns a k-by-n array, each row of which is a random
% permutation of 1:n.
% (ja.doukaku.org Q46)
if nargin<2
    k = 1;
end
[m r] = sort(rand([k n]),2);

4年前に/.J日記界隈で話題になったネタです。
当時のblogへのリンクを晒しておきます。
# 今も拙いって?

see: カードまぜまぜほげふが。

配列にするかリストにするか迷ったのですが、とりあえずリストにしておきました。

import java.util.*;

public class Sample {
    public static List<Integer> bingo(int num) {
        Integer[] deck = new Integer[num];
        for (int i = 0; i < num; i++) {
            deck[i] = i + 1;
        }
        List<Integer> nums = (List<Integer>) Arrays.asList(deck);
        Collections.shuffle(nums);
        return nums;
    }

    public static void main(String[] args) {
        System.out.println(bingo(Integer.parseInt(args[0])));
    }
}

抽出して最後に追加が見あたらなかったので投稿～
Cだとswapすることになるのかな？
めんどそうだからperlで(笑

[10] => 8,10,6,1,3,5,9,4,7,2
[3] => 3,1,2
[2] => 2,1

# rand * 1000 だとうまくいかなかったなぜ？

sub bingo($;)
{
    my $x = shift ;
    my @num = (1 .. $x);
    my $r;
    for( my $n = $x; $n>0; $n --)
    {
        $r = rand; $r *= 1000;
        push(@num, splice(@num, $r % $n, 1) );
    }
    print "[$x] => " . join(",", @num) . "\n";
}
srand;

bingo(10);
bingo(3);
bingo(2);

最初の投稿でえらそうに別解です、なんて書いたけどMATLABのrandpermは実は.mファイル(つまりMATLABで書かれたスクリプト)でその中身は投稿したコードと全く同じだということに気付いた。情けないのであらためて別解。前と同様第二引数で何個生成するか指定する。sortを使う方法よりずいぶん遅い。次のようにすると計算時間の測定と順序が均等かどうかのおおまかな確認ができる。

tic;r=bingo(100,10000);bar(sum(r,1));toc

function r = bingo(n,k)
% r = bingo(n) retruns a random permutation of 1:n.
% r = bingo(n,k) returns a k-by-n array, each row of which is a random
% permutation of 1:n.
% (ja.doukaku.org Q46)
if nargin<2
    k = 1;
end
[s r] = meshgrid(1:k,1:n);
% q = zeros(k,2);
for p = n:-1:2
    q(:,1) = ceil(rand(k,1)*p);
    q(:,2) = p;
    q = q+s(1:2,:)'*n-n;
    r(q) = r(q(:,[2 1]));
end
r = r';

import java.util.*
function bingo(n) {Collections.shuffle(x = list(range(1,n))); x}

println(bingo(10))

Ruby 1.9にはArray#shuffleが存在します

1
2
3

def bingo(n)
  [*1..n].shuffle
end

どこかで見たことがある問題だなぁ…
コードはあまり確かめずに書いた．
配列の参照範囲とか間違ってなければいいけど．

def bingo( n )
  ary = (1..n).to_a
  n.downto(1) {| i |
    e = ary.delete_at( rand( i ) )
    ary.push( e )
  }
  ary
end

import Random (randomRIO)
import Data.List ((\\))

bingo :: Int -> IO [Int]
bingo n = b [1..n] n []
  where b [] n     ret = return ret
        b xs (n+1) ret = do
          r <- randomRIO (0,n)
          let m = xs !! r in b (xs \\ [m]) n (ret ++ [m])

このshuffle関数ではリストは完全にシャッフルされない。
具体的には
[1..1000]というリストを与えた場合。
500 <-> 501, 10 <-> 15
などの近距離では問題ないが
1 <-> 1000
などの遠距離の交換が起こる可能性が極めて低い。

良い実装法だれか教えてください。

rand * 1000
は
rand() * 1000
にすれば動きます。

かっこがないため、
rand( * 1000)
と解釈されているのだと思います。

リハビリを兼ねて、軽めに。

<?php
function bingo($n) {
	$rtn = range(1,$n);
	shuffle($rtn);
	return $rtn;
}

print_r(bingo(25));
?>

>どこかで見たことがある問題だなぁ…

orz…
見たことがない問題を投稿してください…

DouKaku?

重複無し乱数

Posted feedbacks - Flatten