DouKaku?beta

challenge n人中m人が当選するくじ

n人の中から公平にm人を選ぶ、くじ引きプログラムを作ってください。
post comment

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;
	}


lot(1000000,999999)
とかやると止まらない…。

２値でシャッフルは効率悪すぎる…。 

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);
}


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))))))


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)))

こんな感じで使ってください。 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";




    

	

  
  





  
  


  
  






  
  

	

	  
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