n人中m人が当選するくじ
Posted feedbacks - Flatten
Nested Hidden
単純に。
1 2 3 4 5 6 7 8 9 10 11 | def lot(n, m)
rest = Array.new(n) {|i| i }
sel = []
t = if m <= n/2 then m else n-m end
n.downto(n-t+1) do |i|
r = rand(i)
sel << rest[r]
rest.delete_at(r)
end
(if t == m then sel else rest end).sort
end
|
こんなんで。
1 2 3 4 5 6 7 8 9 | import random
def lot(n,m):
if n<m:
print "Error"
return
myset = set()
while len(myset)!=m:
myset.add(random.randint(0,n-1))
return myset
|
適当
1 2 3 4 5 6 | public boolean hoge(int n, int m) {
if ( n < m || n < 0 || m < 0 ) throw new IllegalArgumentException();
long seed = new java.util.Date().getTime() % n;
return seed < m;
}
|
ああ、問題読み間違え。
かならずm人が当たる必要あり。
1 2 3 4 5 6 7 8 9 10 11 12 | public boolean[] lot(int n, int m) {
if ( n < m || n < 0 || m < 0 ) throw new IllegalArgumentException();
boolean[] result = new boolean[n];
for ( int i = 0; i < n; i++ ) result[i] = i < m;
for ( int i = 0; i < n; i++) {
int rnd = (int)(Math.random() * 100) % n;
boolean tmp = result[i];
result[i] = result[rnd];
result[rnd] = tmp;
}
return result;
}
|
Scheme (Gauche) で。素直に。 実行例： gosh> (pick 100 4) (12 17 72 45) gosh> (pick 100 7) (30 68 74 27 58 41 7)
1 2 3 4 5 6 7 8 9 10 | (use srfi-1)
(use srfi-27)
(random-source-randomize! default-random-source)
(define (pick n m)
(let loop ((lis (iota n)) (m m) (r '()))
(cond ((zero? m) r)
((null? lis) (error "pool too small"))
(else (let1 picked (list-ref lis (random-integer (length lis)))
(loop (delete picked lis =) (- m 1) (cons picked r)))))))
|
こんなのどうでしょう？
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Array
def randomize!
rand_array = sort_by { |i| rand }
replace rand_array
end
end
def lot(n, m)
if n >= m
(1..n).to_a.randomize!.slice!(1, m).sort
else
puts "error: n must be bigger than m!"
exit
end
end
|
C++で書いてみたらCしかなかた...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | vector<int>
shuffle(int n, int m)
{
vector<int> ret;
if (n <= 0 || m <= 0 || n < m)
return ret;
vector<int> v(n);
for (int i = 0; i < n; i++)
v[i] = i + 1;
int cnt = 0;
ret.resize(m);
while (cnt < m) {
int idx = rand() % v.size();
int val = v[idx];
v.erase(v.begin() + idx);
ret[cnt++] = val;
}
sort(ret.begin(), ret.end());
return ret;
}
|
上の Ruby コードをもっと短くしてみた。
1 2 3 4 | def lot(n, m)
raise ArgumentError unless m > 0 && n > 0 && m <= n
(1..n).to_a.sort_by {|i| rand}[0, m]
end
|
yuさん/elm200さんのやり方の拡張です。 解説。 まずソーティングの代わりに選択アルゴリズムを使うことで 計算量が線形になります。 また、配列の各要素にランダム値を付加し、 その大小に基づいてソートする方法 (sort_by) だと 厳密には公平になりません。 例えば、2人から1人を選ぶとき 各々に割り振ったランダム値 (r[x] とします) r[0] < r[1] となる確率と r[0] > r[1] となる確率は等確率となりますが わずかに r[0] == r[1] となることがあり、 その場合、例えば先頭からm個とると必ず先の人が選ばれることになるので、 前の人が若干有利になってしまいます。 これは、比較関数自体をランダムにすることで解決します。（多分）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
bool randcmp(const int n1, const int n2)
{ return rand() &1; }
vector<int> lot(int n, int m)
{
vector<int> v(n);
for (int i = 0; i < n; ++i) { v[i] = i+1; }
const int t = (m <= n/2) ? m : n-m;
vector<int>::iterator first = v.begin(), mid = v.begin()+t;
nth_element(first, mid-1, v.end(), randcmp);
if (t < m) { first = mid; mid = v.end(); }
return vector<int>(first, mid);
}
|
ytakenaka
#38()
[
Common Lisp
]
common lispで作ってあります。:-)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | ;
; choose-winners for common lisp version 0.2 by ytakenaka
;
; 使い方: (choose-winners 候補者リスト 選ぶ人の数) => 当選者リスト
; (choose-winners '(john taro mika mick) 2)
; example: => (john taro) リスト内で選ばれたもの
;
; (エラー処理)
; 候補者リスト: ドット付きリスト や リスト以外のもの => nil
; 選ぶ人の数： 候補者リストの長さより大きい => nil
; 選ぶ人の数： 負 => nil
(defun choose-winners (candidates-list number)
(labels ((choose-1 (candit-lst len)
; 候補者リストから一人の当選者と当選者を除いた残りのリストを多値で返す関数
; candit-lst 候補者リスト len 候補者リストの大きさ
(let* ((select-num (random len))
(select-el (nth select-num candit-lst)))
(values select-el (remove select-el candit-lst :count 1))))
(choose-n (lst winners-lst num len)
; 候補者リストからnum人の当選者を選ぶ関数
; lst 候補者リスト winners-lst 当選者リスト
; num 残り当選者数 len 候補者リストの大きさ
(if (zerop num)
; 残り当選者数が０になったときに当選者リストを返す。
winners-lst
(multiple-value-bind (winner rest)
(choose-1 lst len)
; 当選者を当選者リストにくわえて、残りの候補者リストを再帰させる。
(choose-n rest (cons winner winners-lst)
(1- num) (1- len))))))
(and (consp candidates-list)
(null (cdr (last candidates-list)))
(let ((length (length candidates-list)))
(when (and (>= length number) (< 0 number))
(choose-n candidates-list nil number length))))))
|
smeghead
#41()
[
Common Lisp
]
common lispです。 (lot 10 5) => (4 10 8 9 1) (lot 10 5) => (3 10 7 8 9) (lot 10 5) => (5 6 9 2 3)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | (defun lot (n m)
"lot 対象人数 当選者数 => 当選者番号のリスト"
(labels ((range (x acc) ;レンジを作成する関数
(if (zerop x) acc
(range (1- x) (cons x acc))))
(draw (lst acc) ;くじを引く関数
(if (<= m (length acc))
acc
(let* ((winner
(nth (random (length lst) (make-random-state t)) lst))
(loosers
(remove-if #'(lambda (x) (eql winner x)) lst)))
(draw loosers (cons winner acc))))))
(draw (range n nil) nil)))
|
id:amachang
#46()
[
JavaScript
]
こんな感じで使ってください。
alert(['Aさん', 'Bさん', 'Cさん'].lot(2));
1 2 3 4 5 6 | Array.prototype.lot = function(n) {
for(var i=0,r=[];i<n;i++)
with(Math) with(this)
r.push(splice(floor(random()*length), 1)[0]);
return r;
};
|
PHPで。 $m > $n の時、全員が選ばれます
1 2 3 4 5 6 | <?php
function lot($n, $m) {
$a = range(1, $n);
shuffle($a);
return array_slice($a, -$m);
}
|
これでどうだ！
1 2 3 4 5 6 7 8 | sub lot {
my ($n, $m) = @_;
my @list = map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [$_, rand] }
(1 .. $n);
splice(@list, 0, $m);
}
|
つい書いてしまった。
1 2 3 4 5 | sub lot {
my ($n, $m) = @_;
my @a = 0..$n-1;
map { splice @a, int rand scalar @a, 1 } 1..$m;
}
|
てか m 人が常に連続でも題意は満たしてるよね。ということで１ステートメントに。
1 2 3 4 | sub lot {
my ($n, $m) = @_;
splice @{[ 0..$n-1, 0..$n-1 ]}, int rand $n, $m;
}
|
Pythonのrandomモジュールには、与えられたリストをシャッフルするshuffleという関数があります。
1 2 3 4 5 | def lot(n, m):
from random import shuffle
people = range(n)
shuffle(people)
return people[:m]
|
その発想はなかったです。 確かに当選者を連続にとっても、それぞれの人の当選確率は同じなので公平ですね。 その発想をPythonで実装しました。
1 2 3 4 | def lot(n, m):
from random import random
start = int(random() * n)
return (range(n)+range(m))[start:start + m]
|
PostgreSQL以外はよく知りませんが。
1 2 3 4 5 6 7 | =# create function lot(int, int) returns setof int as $$
select * from generate_series(1, $1) order by random() limit $2;
$$ language sql;
=# select * from lot(10, 3);
普通は関数作るまでもなく、
=# select * from generate_series(1, 10) order by random() limit 3;
|
O(m) n < m のとき循環します。
1 2 3 | def lot(n,m)
((r=rand(n))...(r+m)).map {|e| e%n + 1 }
end
|
Pythonのrandomは高機能です。
1 2 3 4 | def lot(n,m):
from random import sample
people = xrange(n)
return sample(people,m)
|
1 2 3 4 | | n m |
n := 10.
m := 5.
^((1 to: n) asArray shuffled allButFirst: m) sort
|
すみません。違ってました(^_^;)。 ÃÂÃÂ allButFirst: ○ first:
実際に使用する時は範囲チェック(1<=m<=n)を追加すること。
1 | (1..n).sort_by{rand}[0,m]
|
Arrow を使えばもっと綺麗に書けるかも。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | import System.Random
shuffle :: [a] -> StdGen -> ([a], StdGen)
shuffle [] g = ([], g)
shuffle xs g = let (needle , g' ) = randomR (0, length xs - 1) g
(left , picked:right) = splitAt needle xs
(unpicked, g'' ) = shuffle (left ++ right) g'
in
(picked:unpicked, g'')
lot :: Int -> Int -> StdGen -> ([Int], StdGen)
lot n m g = let (shuffled, g') = shuffle [1..n] g
in
(take m shuffled, g')
main = do xs <- getStdRandom (lot 1000000 999999)
mapM_ (putStrLn . show) xs
|
echo John Paul George Ringo | awk -v m=2 -f lot.awk
のようにして使います。
1 2 3 4 5 6 7 8 9 10 | function swap(a, b, tmp) { tmp = $a; $a = $b; $b = tmp }
{
n = NF
while (m) {
swap(int(rand() * n + 1), n)
print $n
n--; m--;
}
}
|
我ながら強引すぎるな...
(libcは動くかどうかわかりません汗)「:echo Lot(10, 5)」で実行
1 2 3 4 5 6 7 8 9 10 11 12 | fun! Lot(n, m)
let v = range(1, a:n)
while len(v) > a:m
if has('win32')
let r = libcallnr("msvcrt", "rand", 0)
else
let r = libcallnr("libc", "rand", 0)
endif
silent! call remove(v, (r % 10))
endwhile
return v
endfun
|
あ、ハードコーディング...orz
1 2 3 4 5 6 7 8 9 10 11 12 | fun! Lot(n, m)
let v = range(1, a:n)
while len(v) > a:m
if has('win32')
let r = libcallnr("msvcrt", "rand", 0)
else
let r = libcallnr("libc", "rand", 0)
endif
silent! call remove(v, (r % len(v)))
endwhile
return v
endfun
|
srand(time(NULL));
sel1(M, N);
って感じで
1 2 3 4 5 6 7 8 | void sel1(unsigned long m, unsigned long n)
{
unsigned long i, orgN=n;
for(i=1; i<=orgN; ++i){
if((double)rand()/(RAND_MAX+1) < (double)m/n){ printf("%lu\n", i); --m; }
--n;
}
}
|
一応O(nm)になってるかな？
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | #!/usr/local/bin/perl
use strict;
use warnings;
use Data::Dumper;
my $nmax = shift;
my $mmax = shift;
my @winner;
#warn "selecting $nmax from $mmax\n";
for my $n ( 0 .. $nmax - 1 ) {
my $count = 0;
for my $m ( 1 .. $mmax ) {
next if grep { defined $_ and $_ == $m } @winner;
if ( rand( $count ) < 1 ) {
$winner[$n] = $m;
}
$count++;
}
}
print join( "\n", @winner) , "\n";
|
進捗表示と範囲チェックを追加。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #!/usr/local/bin/perl
use strict;
use warnings;
use Data::Dumper;
my $nmax = shift;
my $mmax = shift;
if ( $nmax >= $mmax ) {
print "$_\n" for ( 1 .. $mmax );
exit;
}
my @winner;
#warn "selecting $nmax from $mmax\n";
for my $n ( 0 .. $nmax - 1 ) {
print STDERR '.';
my $count = 0;
for my $m ( 1 .. $mmax ) {
next if grep { defined $_ and $_ == $m } @winner;
if ( rand( $count ) < 1 ) {
$winner[$n] = $m;
}
$count++;
}
}
print STDERR "\n";
print join( "\n", @winner) , "\n";
|
rubikitch
#191()
[
Common Lisp
]
CL-USER> (lot 9999 4) (6921 3598 7669 9882) CL-USER> (lot 9999 4) (46 7796 5867 7725) CL-USER> (lot 9999 4) (6973 5502 1591 5060) CL-USER> (lot 9999 4) (23 5583 9408 419) CL-USER> (lot 9999 4) (1785 6633 7933 8614) CL-USER> (lot 9999 4) (3871 7900 7919 1041)
1 2 3 4 5 6 | (defun lot (n m)
(let ((lot (loop for i from 1 to n collect i)))
(loop repeat m collect
(let ((x (nth (random (length lot)) lot)))
(setf lot (delete x lot))
x))))
|
jってこれでよかった(一様にランダムになる)か？
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | public static bool[] MakeDrawing(int n, int m)
{
if (n < 0) throw new ArgumentException();
if (m < 0 || m > n) throw new ArgumentException();
bool[] result = new bool[n];
Random r = new Random();
for (int i = 0; i < n; i++)
{
int j = r.Next(i + 1);
result[i] = result[j];
result[j] = (i < m);
}
return result;
}
|
(lot m n)でm人中n人分の当選番号（1～m）をリストで返します。。 (lot m n lst)でm人中n人分、lstから当選者を抽出したリストを返します。 lstがmより長かったり短かったりしたらnilを返します:p m<nの時は全員当選します。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | (defun lot (n m &optional (lst (let ((i 0))
(mapcar #'(lambda (x) (+ (incf i) x))
(make-list n :initial-element 0)))))
(and
(= (length lst) n)
(labels
((pickup (lst m)
(labels
((pickup1 (lst n m acc)
(if (or (zerop n) (zerop m))
acc
(let ((r (random n)))
(if (zerop r)
(pickup1 (cdr lst)
(1- n)
(1- m)
(cons (car lst) acc))
(pickup1 (nconc (subseq lst 0 r)
(subseq lst (1+ r)))
(1- n)
(1- m)
(cons (nth r lst) acc)))))))
(pickup1 lst n m nil))))
(pickup lst m))))
|
今ひとつエレガントじゃないなぁ。
1 2 3 4 5 6 7 8 9 10 11 12 13 | # -*- coding: utf-8 -*-
import random
def getRandList(x):
l = range(x)
random.shuffle(l)
return l
def chusen(n,m):
return getRandList(n)[:m]
print chusen(10,5)
print chusen(50,10)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | open System;;
open List;;
let rec take n ls =
match n, ls with
| n, _ when n <= 0 -> []
| _, [] -> []
| n, (hd::tl) -> hd :: take (n-1) tl;;
let shuffle ls =
let rnd = new Random() in
sort (fun x y-> rnd.Next(-1,2)) ls;;
let choice m n = take m (shuffle (init n (fun x -> x)));;
|
C++ならstd::random_shuffle使えばいいね。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
int n = 10, m = 3, seed = 1;
Random r = new Random(seed);
foreach (int i in GetRandom(n, m, r))
Console.WriteLine(i);
}
public static int[] GetRandom(int n, int m, Random r)
{
n = Math.Max(n, 0);
m = Math.Min(m, n);
List<int> lst = new List<int>(n);
for (int i = 0; i < n; ++i) lst.Add(i);
for (int i = 0; i < m; ++i)
{
int k = r.Next(n - i) + i;
int t = lst[i];
lst[i] = lst[k];
lst[k] = t;
}
lst.RemoveRange(m, n - m);
lst.Sort();
return lst.ToArray();
}
}
|
とりあえず一発でやるならこうかなあ。
1 2 3 4 5 | import scala.util.Sorting
def lot(n:Int, m:Int):Seq[Int] = {
Sorting.stableSort[Int, Double](List.range(0,n),{x=>Math.random}).take(m)
}
println(lot(2,10).mkString(","))
|
kkobayashi
#688()
[
R
]
n <- 10 m <- 5 sample(n, m) [1] 3 1 9 6 10
1 | sample(n, m)
|
選ばれた人を消去して重複回避。不細工だなぁ。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | import java.util.List;
import java.util.ArrayList;
import java.util.Random;
public class LotGame {
public List<Integer> lot(int n, int m) {
List<Integer> result = new ArrayList<Integer>();
List<Integer> base = range(n);
Random random = new Random();
for (int i = 0; i < m; i++) {
int j = random.nextInt(base.size() - 1);
result.add(base.get(j));
base.remove(j);
}
return result;
}
private List<Integer> range(int n) {
List<Integer> result = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
result.add(i);
}
return result;
}
public static void main(String[] args) {
for (int i : new LotGame().lot(10, 5)) {
System.out.println(i);
}
}
}
|
rubikitch
#818()
[
Emacs Lisp
]
1 2 3 4 5 6 | (defun lot (n m)
(let ((lot (loop for i from 1 to n collect i)))
(loop repeat m collect
(let ((x (nth (random (length lot)) lot)))
(setf lot (delete x lot))
x))))
|
沢渡 みかげ
#834()
[
Mathematica
]
Mathematica6で追加された関数を使用．
1 | choice[n_, m_] := RandomSample[Range[n], m];
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | function lot(n, m)
math.randomseed(os.time())
lot = {}
for i = 1, n do
table.insert(lot,i)
end
ret = {}
for i = 1, m do
pos = math.random(table.getn(lot))
x = lot[ pos ]
table.remove(lot, pos)
table.insert(ret,x)
end
return ret
end
function print_lot(n, m)
table.foreach(lot(n, m), function(k,v) print(v) end)
end
print_lot(9999, 4)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | module doukaku;
private import std.stdio;
private import std.random;
void remove(int[] ary, int pos) {
if (ary.length != pos+1)
for (int i=pos+1; i < ary.length; i++)
ary[i-1] = ary[i];
ary.length = ary.length - 1;
}
int[] lot(int n, int m) {
int i;
int[] lot, ret;
for (i=1; i<=n; i++) lot ~= i;
for (i=1; i<=m; i++) {
int pos = rand() % lot.length;
int x = lot[pos];
remove(lot, pos);
lot.length = lot.length - 1;
ret ~= x;
}
return ret;
}
void print_lot(int n, int m) {
foreach(x; lot(n, m)) writefln(x);
}
void main() {
print_lot(9999, 4);
}
|
やっていることはMathematica版と同じですね。
出力例：
>> lot(100, 10)
ans =
80 42 71 97 51 4 81 94 2 92
1 2 3 4 | function x = lot(n, m)
A = randperm(n);
x = A(1:m);
end
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | { Free Pascal + Run-Time Library (rtl)
2 args
kuji n m
}
program kuji;
uses
SysUtils;
Var
n, m : Cardinal;
begin
if ParamCount <> 2 then Exit;
n := StrToInt(paramstr(1));
m := StrToInt(paramstr(2));
if n < m then Exit;
Writeln('# n=', IntToStr(n), ' m=', IntToStr(m));
Randomize;
for n := n downto 1 do
begin
if Random(n)+1 <= m then
begin
WriteLn(IntToStr(n));
Dec(m);
end;
end;
end.
|
もうすこし調べたら、そのものずばりの関数がありました。がっかり。
出力例：
>> randsample(100,10)
ans =
96
6
71
46
81
56
34
22
80
88
1 | randsample(n,m)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | math.randomseed(os.time())
function iota(n)
local t = {}
for i=1,n do
table.insert(t, i)
end
return t
end
function lot(m, n)
function pick(winners, rest, m)
if m == 0 then
return winners
else
local picked = table.remove(rest, math.random(#rest))
table.insert(winners, picked)
return pick(winners, rest, m-1)
end
end
return pick({}, iota(n), m)
end
function show_array(t)
print("["..table.concat(t, " ").."]")
end
show_array(lot(arg[1], arg[2]))
|
kacchi
#1166()
[
Emacs Lisp
]
(lot 100 3) =>(99 21 16)
1 2 3 | (defun lot (n m)
(let ((v (vconcat (number-sequence 0 (- n 1)))))
(nthcdr (- n m) (append (shuffle-vector v) nil))))
|
勉強し始めているので、とりあえず投稿
1 2 3 4 5 6 7 8 9 10 | private function execute(n:int, m:int):void {
var res:Array = [];
for (var i:int = 0; i < m;) {
var r:int = Math.floor(Math.random() * n);
if (res.indexOf(r) >= 0) continue;
i++;
res.push(r);
}
Alert.show(res.toString());
}
|
基本的なリスト操作述語が無いので、長たらしくなります。 リスト生成→乱打舞頭→頭から順番にN個という流れです。 randomizeは、M人分だけすれば良い気もします。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | serial(S,E,[]):-S > E.
serial(S,E,[S|R]):-succ(S,S1),serial(S1,E,R).
remove([L|Ls],1,L,Ls).
remove([],_,_,_):-fail.
remove([L|Ls],N,E,[L|R]):-succ(N1,N),remove(Ls,N1,E,R).
randomize([X],[X]).
randomize(L,R):-random(N),length(L,Ll),Nx is floor(N * Ll) + 1,remove(L,Nx,Le,Rs),randomize(Rs,Rss),R=[Le|Rss].
take(_,0,[]).
take([L|Ls],N,[L|R]):-succ(N1,N),take(Ls,N1,R).
lot(N,M,R):-serial(1,N,L0),randomize(L0,L1),take(L1,M,R).
:-lot(20,5,R),writeln(R),halt.
|
#1248は無かったことに。
Nまでの列生成→ランダムにM個取り出し です。
1 2 3 4 5 6 7 8 9 10 11 12 13 | serial(S,E,[]):-S > E.
serial(S,E,[S|R]):-succ(S,S1),serial(S1,E,R).
remove([L|Ls],1,L,Ls).
remove([L|Ls],N,E,[L|R]):-succ(N1,N),remove(Ls,N1,E,R).
randomize(0,_,[]):-!.
randomize(I,L,R):-random(N),length(L,Ll),Nx is floor(N * Ll) + 1,remove(L,Nx,Le,Rs),succ(I1,I),
randomize(I1,Rs,Rss),R=[Le|Rss].
lot(N,M,R):-serial(1,N,L0),randomize(M,L0,R).
:-lot(20,5,R),writeln(R),halt.
|
匿名
#1405()
[
JavaScript
]
元の配列には影響を与えない alert(["ほ","げ","foo","bar"].cnr(2));
1 2 3 4 | Array.prototype.cnr = function(n)
{
return this.sort(function(){return Math.random()-0.5}).slice(0,n-this.length);
}
|
1 2 3 4 5 6 | import java.util.*
function lot(n, m){
l = list(range(0,n-1))
Collections.shuffle(l)
l[0..m-1]
}
|
gawk -f lottery.awk <m> <n> [seed] として使うと、0～(m-1)の数字からランダムでn個表示します。 seedはオプションです。 ex) gawk -f lottery.awk 10 3 0 4 7 任意の数字が選ばれる確率は、(残りの当選数)/(残りの総数)となります。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | BEGIN {
m = ARGV[1]
n = ARGV[2]
if(ARGC == 4) {
srand(ARGV[3])
} else {
srand()
}
for(i = 0; i < m; i++) {
if(rand() * (m - i) < n) {
print i
n--
}
if(n == 0) {
break
}
}
}
|
mがnに近くなると効率悪くなりますが。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | Public Sub DrawLots(ByVal n As Integer, ByVal m As Integer)
If n < m OrElse n < 1 Then
Exit Sub
End If
Dim list As New List(Of Integer)
Dim r As New Random
Do
Dim v As Integer = r.Next(1, n + 1)
If Not list.Contains(v) Then
list.Add(v)
If list.Count = m Then
Exit Do
End If
End If
Loop
list.Sort()
For Each i As Integer In list
Console.WriteLine(i)
Next
End Sub
|
SWI-Prologです。
長さnのリストからm個をランダムに選びます。
リストの最初の要素をm/nの確立で選び、
選ばれた ⇒ 残りの長さn-1のリストからm-1個を選ぶ
選ばれなかった ⇒ 残りの長さn-1のリストからm個を選ぶ
という再帰的なアルゴリズムです。
結局は普通のランダム・サンプリングと同じです。
これだとリストでも計算量が線形時間になります。
実行例（n=100, m=5の場合）：
:- numlist(1, 100, L), sample(L, 5, Samples).
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
Samples = [1, 6, 36, 68, 85]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | %% sample(+List1, +N, -List2)
%
% List2はList1からランダムにN個の要素を選んだもの
sample(Xs, N, Ys) :-
length(Xs, Len),
N1 is max(0, min(N, Len)),
sample_aux(Xs, Len, N1, Ys).
sample_aux(_, _, 0, []) :- !.
sample_aux([X|Xs], Len, N, [X|Ys]) :-
random(Len) < N, !,
Len0 is Len - 1,
N0 is N - 1,
sample_aux(Xs, Len0, N0, Ys).
sample_aux([_|Xs], Len, N, Ys) :-
Len0 is Len - 1,
sample_aux(Xs, Len0, N, Ys).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | def lottery(n,m) {
rand = new Random()
all = 0..<n
(1..m).inject([]) { wins, _bottom ->
win = all[rand.nextInt(all.size())]
all -= win
wins + win
}
}
println lottery(4,1)
println lottery(4,2)
println lottery(4,3)
println lottery(4,4)
|
ナイーブに。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | import System.Environment
import System.Random
main :: IO ()
main = do { (p:q:_) <- getArgs
; let (n,m) = (read p,read q)
; newStdGen >>= loop n m [1..n] >>= print
}
loop _ 0 _ _ = return []
loop n m s g
= case randomR (0,n-1) g of
(n',g') -> case splitAt n' s of
(xs,y:ys) -> loop (n-1) (m-1) (xs++ys) g' >>= return . (y:)
|
1 2 | use List::Util qw/shuffle/;
sub lot {($n,$m)= @_; (shuffle(1..$n))[1..$m];}
|
1 2 3 4 5 6 7 8 9 10 11 12 13 | def kujibiki(users, m)
raise ArgumentError unless users.size >= m
results=[]
m.times{
v=((users.size * rand()).to_i)
results << users.delete_at(v)
}
results
end
users = [0,1,2,3,4,5,6,7,8,9]
p kujibiki(users, 10)
|
GPU向けの言語であるCUDAで作成してみました。 誰もうれしくないと思いますが、こんなのもあるんだね、とでも思って下さい。 CUDAに乱数生成関数がないため、本家サンプルの乱数生成を利用しています。 コア部分のアルゴリズムは#54の解釈を利用したので超簡単ですが、GPU駆動のコードのため伸びまくりです。かっこ悪い。
see: MersenneTwister@NVIDIA CUDA SDK Code Samples
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | float *d_Rand; // GPU上で利用する変数
float *h_Rand=NULL; // CPU上で利用する変数
// GPU上で乱数を生成するための関数。中身は本家サンプルを利用しているので割愛。
// d_Rand/h_Randに乱数がぶち込まれると解釈してください。
void initMTGPU()
{
CUDA_SAFE_CALL( cudaMalloc((void **)&d_Rand, RAND_N * sizeof(float)) );
RandomGPU<<<32, 128>>>(d_Rand, N_PER_RNG, SEED);
CUT_CHECK_ERROR("RandomGPU() execution failed\n");
CUDA_SAFE_CALL(cudaMallocHost((void**)&h_Rand, sizeof(float)*RAND_N));
CUDA_SAFE_CALL(cudaMemcpy(h_Rand, d_Rand, sizeof(float)*RAND_N, cudaMemcpyDeviceToHost));
}
// コア部分。#54の解釈を利用。乱数の種は適当に設定。
#define RAND_SEED 5
__global__ void gpu(float *d_Random, int *answer, int n, int m)
{
int i, j=0;
int begin = d_Random[RAND_SEED] * (float)n;
for(i=begin; i<begin+m; i++){
answer[j++] = i % n;
}
}
// くじ引き関数。answerに答えの数列が格納されます。
int lot(int *answer, int n, int m)
{
CUT_DEVICE_INIT();
initMTGPU();
int *d_mem;
CUDA_SAFE_CALL(cudaMalloc((void**)&d_mem, sizeof(int)*m));
CUDA_SAFE_CALL(cudaMemcpy(d_Rand, h_Rand, sizeof(float)*RAND_N, cudaMemcpyHostToDevice));
dim3 threads(1, 1, 1);
dim3 grid(1,1,1);
gpu<<< grid, threads >>>(d_Rand, d_mem, n, m);
CUDA_SAFE_CALL( cudaThreadSynchronize() );
CUT_CHECK_ERROR("Kernel execution failed");
CUDA_SAFE_CALL(cudaMemcpy(answer, d_mem, sizeof(int)*m, cudaMemcpyDeviceToHost));
CUDA_SAFE_CALL(cudaFree(d_mem));
CUDA_SAFE_CALL(cudaFreeHost(h_Rand));
return 0;
}
#define N_ALLSIZE 100
#define N_HITSIZE 5
int main(int argc, char** argv)
{
int answer[N_HITSIZE];
lot(answer, N_ALLSIZE, N_HITSIZE);
int i;
for(i=0; i<N_HITSIZE; i++){
printf(" %d", answer[i]);
}
printf("\n");
}
|
omoikani
#3154()
[
StandardML
]
綺麗じゃないけど。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 | fun choice n m =
let
val rnd = Random.rand (Time.toNanoseconds (Time.now ()), m)
fun loop 0 m' = m'
| loop n' m' =
let
val number = Random.randRange (1, n) rnd
in
if List.exists (fn x => x = number) m' then loop n' m' else loop (n' - 1) (number::m')
end
in
loop m []
end
|
円順列から切り取る方式。
1 2 3 4 5 6 7 | どう書く４＝「｜ｎ ｍ｜
「｜候補 当選 番｜
「｜ｘ｜候補！(ｘ)入れる」！(ｎ)繰り返す。
「ｍ＞０」！の間「番＝番％ｎ＋１。ｍ＝ｍ－１。当選！(候補！(番)見る)入れる」実行。
」！(配列！作る)(配列！作る)(乱数(ｎ))実行」。
ラベル！(どう書く４！13 11 実行)作る。
|
faultier
#3925()
[
Objective-C
]
アレイのuniqと似てるなぁ。 ちなみにn < mだと全員当選します。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #import <Foundation/Foundation.h>
#import <stdio.h>
@interface NSArray (Random)
- (NSArray *)objectsAtRandom:(int)number;
@end
@implementation NSArray (Random)
- (NSArray *)objectsAtRandom:(int)m
{
int n = [self count];
id selected;
if (m >= n)
{
selected = self;
}
else
{
srand(time(nil));
NSMutableDictionary* winnerTable = [NSMutableDictionary dictionary];
selected = [NSMutableArray array];
id winner;
while ([selected count] < m)
{
winner = [self objectAtIndex:(rand()%n)];
if (![winnerTable objectForKey:winner])
{
[winnerTable setObject:winner forKey:winner];
[selected addObject:winner];
}
}
}
return selected;
}
@end
int main(int argc, const char * argv[])
{
NSAutoreleasePool* pool = [NSAutoreleasePool new];
if (argc < 3) {
printf("Usage: %s n player1[,player2...]\n", argv[0]);
return 1;
}
NSArray* players = [[NSString stringWithCString:argv[2] encoding:NSUTF8StringEncoding] componentsSeparatedByString:@","];
for (id winner in [players objectsAtRandom:atoi(argv[1])])
{
printf("%s\n", [winner cStringUsingEncoding:NSUTF8StringEncoding]);
}
[pool release];
return 0;
}
|
1 2 3 4 5 6 7 8 | 100から10をくじ引きして表示
●くじ引き(mからnを)
t1とは配列;t2とは配列
もし(n>m)ならば,""で戻る
(m)回,t1[回数-1]=回数-1
t1を配列シャッフル
(n)回,t2[回数-1]=t1[回数-1]
t2で戻る
|
yield句の便利さを最近知りました。 yield句を用いると、この手のコードを簡単にかけますね。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | using System;
using System.Collections;
class Program
{
static void Main(string[] args)
{
int n = 10, m = 4;
foreach( var val in GetIterator(n,m) ) Console.WriteLine( val );
}
public static System.Collections.IEnumerable GetIterator( int n, int m)
{
Random r = new Random();
ArrayList list = new ArrayList();
for(int i=1; i<=n ; i++) list.Add( i );
for(int i=0; i<m ; i++ )
{
var temp = list[r.Next(list.Count)];
list.Remove(temp);
yield return temp;
}
}
}
|
j言語です。二項演算子として使います。 10 f 5 9 5 7 10 1 10 f 5 3 8 4 6 2 10 f 5 6 10 4 7 9 10000 f 5 7973 8054 1191 450 7334
1 | f=.4 :'>:y?x'
|
長さNのリストをシャッフルして、先頭からM個を取り出します。
1> c(n_m).
{ok,n_m}
2> n_m:n_m(10, 3).
[3,1,9]
3> n_m:n_m(10, 3).
[1,6,7]
1 2 3 4 5 6 7 8 9 10 | -module(n_m).
-export([n_m/2]).
shuffle(List, 0) -> List;
shuffle(List, N) ->
R = lists:nth(random:uniform(length(List)), List),
L = [R | [X || X <- List, X =/= R]],
shuffle(L, N - 1).
n_m(N, M) -> lists:sublist(shuffle(lists:seq(1, N), N), M).
|
Ioを使ってみる．
1 | lot := method(n, m, 1 to(n) asList shuffle slice(0, m))
|
Integerの動的配列をtypeで定義しています。 Delphiは配列操作が苦手なので、できるだけ使わないようにしています。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | type
TDynIntArray = array of Integer;
function lot(n, m: Integer): TDynIntArray;
function NumInArray(num: Integer; arr :TDynIntArray): Boolean;
var
x: Integer;
begin
Result := False;
for x in arr do
if x = num then
Result := True;
end;
var
people: TDynIntArray;
i: Integer;
num_lot: Integer;
begin
SetLength(people, m);
Randomize;
for i := 0 to m - 1 do
begin
repeat
num_lot := Random(n) + 1;
until not NumInArray(num_lot, people);
people[i] := num_lot;
end;
Result := people;
end;
|
選んだ数が、結果の配列になければ追加します。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | n = 10
m = 3
results = []
if 1 <= m && m <= n
i = 0
while i < m
chosen_one = rand(n) + 1
unless results.include?(chosen_one)
results << chosen_one
i += 1
end
end
p results.sort
else
puts "mは1以上n以下で指定してください。"
end
|
Arcです。
お題46の「重複無し乱数」で定義したbingoを使用しています。
(lot 999 4)
;=> (484 286 880 186)
;...
;=> (699 151 312 134)
お題46の「重複無し乱数」で定義したbingoを使用しています。
(lot 999 4)
;=> (484 286 880 186)
;...
;=> (699 151 312 134)
see: bingo
1 2 | (def lot (n m)
(firstn m (bingo n)))
|
動作環境 Fedora7 Perl5.8.8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | #!/usr/bin/perl
use strict;
exit main();
sub main{
if(@ARGV != 2){
print "usage: perl 3360.pl <total-number> <target-number>\n";
return 1;
}
my $rtn = 0;
if($rtn = is_num($ARGV[0])){
print "$ARGV[0] not integer\n";
return $rtn;
}
if($rtn = is_num($ARGV[1])){
print "$ARGV[1] not integer\n";
return $rtn;
}
if($ARGV[0] <= $ARGV[1]){
print "$ARGV[0] isn't greater than $ARGV[1]\n";
return 3;
}
my $total = $ARGV[0];
my $target = $ARGV[1];
my $rand_numbers = get_rand_number($total,$target);
print join "\n", @$rand_numbers;
return 0;
}
sub is_num{
my ($num) = shift;
if($num !~ / [0-9]+$/){
return 2;
}
return 0;
}
sub get_rand_number{
my ($total,$target) = @_;
my $numbers = [];
my $rand = undef;
for(my $i=0; $i<$target; $i++){
$rand = int(rand($total))+1;
if(!grep { /^$rand$/ } @$numbers){
push @$numbers, $rand;
}
else{
redo;
}
}
return $numbers;
}
|
Nemo
#6546()
[
PostScript
]
n 人中1人を抜き出し、更に残りから 1人を抜きだし、を繰り返しです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | %!PS
/Kuji { % n m Kuji [numbers]
[ 3 1 roll
[
1 1 5 -1 roll { } for
dup 2 add -1 roll
{
counttomark dup rand exch mod roll
counttomark 1 add 1 roll
} repeat
] pop
]
} bind def
% ----- Test Code ---------
100 20 Kuji ==
|
しょーた
#6741()
[
PowerShell
]
とりあえず。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | function lot($n, $m) {
if ($n -ge $m) {
$randomgenerator = New-Object Random
$source = 1 .. $n
$limit = $n
$result = @()
foreach ($i in 1 .. $m) {
$limit -= 1
$ii = $randomgenerator.Next($limit + 1)
$result += $source[$ii]
if ($ii -gt 0) {
$srclow = $source[0 .. ($ii - 1)]
} else {
$srclow = @()
}
if ($ii -lt $limit) {
$srchi = $source[($ii + 1) .. $limit]
} else {
$srchi = @()
}
$source = $srclow + $srchi
}
}
return $result | sort
}
|
random.shuffleは便利ですが、それだと味気ないので‥‥。
Rubyの「Enumerable#sort_by { rand }」と同じ発想でシャッフルしてみました。
1 2 3 4 5 6 7 8 9 10 11 12 | import random
import sys
def lot(n, m):
a = [(x, random.random()) for x in range(1, n + 1)]
a.sort(lambda x, y: cmp(x[1], y[1]))
return [x[0] for x in a][0:m]
if len(sys.argv) != 3:
print "usage: %s all pickup" % (sys.argv[0])
else:
print lot(int(sys.argv[1]), int(sys.argv[2]))
|
Limbo習作。 rand, daytime, stringモジュールのテスト。 すでにLimboでいっぱい書いている方がいるようなので、遠慮がちに・・・
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | # file: d4.b
# Lottery
implement d4;
include "sys.m";
include "draw.m";
include "string.m";
include "rand.m";
include "daytime.m";
sys: Sys;
usage: fn(prog: string);
d4: module
{
init: fn(ctxt: ref Draw->Context, argv: list of string);
};
init (ctxt: ref Draw->Context, argv: list of string)
{
str: String;
rand: Rand;
time: Daytime;
n, m, i, val: int;
prog: string;
sys = load Sys Sys->PATH;
str = load String String->PATH;
rand = load Rand Rand->PATH;
time = load Daytime Daytime->PATH;
prog = hd argv;
argv = tl argv;
if(argv == nil){
usage(prog);
return ;
}
(n, nil) = str->toint(hd argv, 10);
argv = tl argv;
if(argv == nil){
usage(prog);
return;
}
(m, nil) = str->toint(hd argv, 10);
if(m == 0 || n == 0 || n < m){
usage(prog);
return;
}
flags := array [n] of int;
for(i = 0; i < n; i++){
flags[i] = 0;
}
rand->init(time->now());
while(m > 0){
val = rand->rand(n);
if(flags[val] == 0){
flags[val] = 1;
m --;
}
}
for(i = 0; i < n; i++){
if(flags[i]){
sys->print("%d ", i + 1);
}
}
sys->print("\n");
}
usage (prog: string)
{
sys->print("usage: %s n m\n", prog);
}
|
see: [ruby-list:40892]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #!/bin/bash
function randsample() {
local n=$1
local m=$2
local -a array
local -i i j tmp
for ((i = 0; i < n; i++)) {
array[i]=$i
}
# shuffle
for ((i = 0; i < n; i++)) {
((j = RANDOM % (i + 1),
tmp = array[i], array[i] = array[j], array[j] = tmp))
}
# print top m
for ((i = 0; i < m && i < n; i++)) {
echo ${array[i]}
}
}
randsample 100 10
|
GNU coreutilsのshufで。
1 2 3 4 5 6 | #!/bin/sh
randsample() {
seq $1 | shuf | head -n $2
}
randsample 100 10
|
m > n でも n > m でも引数が１つでも公平に。shuffle使用。
1 2 3 4 5 6 7 8 9 10 | def kuji(n, m = n)
m, n = n, m if m > n
srand
[*(1..n)].shuffle[0..(m-1)]
end
kuji(10, 3).sort # => [1, 2, 3]
kuji(3, 10).sort # => [2, 4, 6]
kuji(10, 10) # => [6, 7, 9, 1, 10, 4, 2, 3, 5, 8]
kuji(10) # => [10, 2, 8, 6, 1, 9, 4, 3, 5, 7]
|
こっちの方がRubyっぽいかしらん？ IntegerクラスとRangeクラスに定義してみました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class Integer
def kuji(m = self)
srand
[*(1..self)].shuffle.first(m)
end
end
class Range
def kuji(m = self)
srand
[*self].shuffle.first([*m].last)
end
end
#Integer
10.kuji(3) # => [2, 6, 10]
10.kuji # => [9, 10, 6, 1, 2, 3, 4, 5, 8, 7]
#Range
(1..10).kuji(3) # => [5, 4, 2]
(1..10).kuji # => [9, 6, 7, 4, 8, 5, 1, 10, 2, 3]
|
いまさら投稿。
1 2 3 4 5 6 7 | def select(n, m){
def list = 1..n as ArrayList
Collections.shuffle list
list[0..<m]
}
println select(5, 3)
|
PHP勉強中
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | <?php
print <<< END_DOC
<HTML>
<HEAD><title>doukaku 04</title>
</HEAD><BODY>
END_DOC;
function doukaku04($n, $m)
{
$a = array();
for($i = 0; $i < $n; $i++){
$r = mt_rand(0, $i - 1);
array_push($a, $a[$r]);
$a[$r] = $i;
}
return array_slice($a, 0, $m);
};
foreach(doukaku04(10, 5) as $d){
print "$d,";
}
print <<< END_DOC
</BODY>
</HTML>
END_DOC;
?>
|
にしお
#3360()
Rating0/0=0.00
[ reply ]