4

競技のブラケットシートを処理するためのアルゴリズムを構築しようとしています。一連の数値を調べる必要があります。番号ごとに選手名が入ります。番号は選手にランダムに割り当てられますが、番号の組み合わせは常に同じでなければなりません。奇数と偶数の 2 つのグループ、つまり A と Bがあります。

次のように正確な方法で数値を反復するための適切なアルゴリズムが見つからないという唯一の問題:

Group A:
--------
  1
  17

  9
  25
------
  5
  21

  13
  29
------
  3
  19

  11
  27
------                         
  7
  23

  15
  31


Group B:
--------
  2
  18

  10
  26
------                          
  6
  22

  14
  30
------   
  4
  20

  12
  28
------
  8
  24

  16
  32

上記の出力を取得する方法のアドバイスや例を教えてください。

編集1：

上記の例は、32人の選手のブラケット シートです。4、8、16、64、または128人のアスリート用のシートを使用する場合も、同じロジックを適用する必要があります。

編集2：

4 人の選手用のシートと 16 人の選手用のシートの例で、より明確にしましょう。

4 選手用シート:

Group A:
--------
  1
  3

Group B:
--------
  2
  4

16 選手のシート:

Group A:
--------
  1
  9

  5
  13
------
  3
  11

  7
  15

Group B:
--------
  2
  10

  6
  14
------                              
  4
  12

  8
  16

編集3：

最後の部分は、アスリート名とそのステータスを含む配列を計画していることです。ステータスとは、アスリートが以前にチャンピオンであった場合 (強い)、ステータスとして1を取得し、アスリートの以前の業績が不明または最小限 (弱い) の場合、ステータスは0です。そうすることで、最強のアスリートを異なるグループに分けて、最初の戦いで互いに戦わず、準決勝または決勝に近づいてお互いに会うことができるようにすることができます.

PHP 配列の例:

$participants = array(
array("John", 0),
array("Gagan", 0),
array("Mike Tyson", 1),
array("Gair", 0),
array("Gale", 0),
array("Roy Johnes", 1),
array("Galip", 0),
array("Gallagher", 0),
array("Garett", 0),
array("Nikolai Valuev", 1),
array("Garner", 0),
array("Gary", 0),
array("Gelar", 0),
array("Gershom", 0),
array("Gilby", 0),
array("Gilford", 0)
);

この例から、ステータス1を持つ人は異なるグループ、つまりAとBに属している必要があることがわかります。しかし、奇数と偶数の2 つのグループしかなく、この例では3 人の強いアスリートがいます。したがって、そのうちの 2 つは同じグループになります。最終的な結果は、同じグループに入った 2 人の強力なアスリートが、最初の戦いで会ってはならないということでなければなりません(つまり、2 人は同じ番号のペアにならず、互いにできるだけ離れることを意味します)。 、したがって、2回目の戦いでも会うことはありません）。

次に、ランダムに、配列を再配置し、アスリートをブラケット シートに送信することを計画しています。毎回、異なる番号で、フラグ1を持つ選手は異なるグループに移動し、および/または最初の戦いで決して会うことはありません。時間、同じ番号のペアに割り当てられたアスリートの名前。

4

3 に答える 3

4

参加者の数は常に 2 の累乗であることを考慮すると、このコードは期待どおりの順序で表示されるはずです。

function getOrder($numberOfParticipants) {
    $order = array(1, 2);

    for($i = 2; $i < $numberOfParticipants; $i <<= 1) {
        $nextOrder = array();
        foreach($order as $number) {
            $nextOrder[] = $number;
            $nextOrder[] = $number + $i;
        }
        $order = $nextOrder;
    }

    return $order; // which is for instance [1, 17, 9, 25, and so on...] with 32 as argument
}

そのしくみについて、参加者を倍増させた場合の様子を見てみましょう。

Participants | Order
           2 | 1   2
           4 | 1   3=1+2   2   4=2+2
           8 | 1   5=1+4   3   7=3+4   2   6=2+4   4   8=4+4
         ... |
           N | 1         X         Y         Z         ...
          2N | 1   1+N   X   X+N   Y   Y+N   Z   Z+N   ...

私が使用したアルゴリズムは、まったく同じロジックです。[1, 2]のみを含む配列から始め、$i実際にはこの配列のサイズです。次に、適切な数の参加者が含まれる行に到達するまで、次の行を計算します。

補足:$i <<= 1と同じことを行い$i *= 2ます。詳細については、ビット演算子に関するドキュメントを参照してください。

強いアスリートについては、可能な限りランダム性を維持したいので、ここに解決策があります（おそらく最適ではありませんが、それが私が最初に考えたことです）：

  1. 2 つのアレイを作成します。1 つはストロング、もう 1 つはウィークです。
  2. ストロングがない場合、またはストロングが 1 つしかない場合は、配列全体をシャッフルして 8 に進みます。
  3. 弱いものよりも強いものが多い場合(あなたのケースで発生する可能性があるかどうかはわかりませんが、申し訳ありませんが安全であることをお勧めします)、強いものをシャッフルし、最後のものを弱いものに置き、両方の配列が同じサイズになるようにします
  4. それ以外の場合は、ストロングをnull要素で埋めて、配列サイズが 2 の累乗になるようにしてからシャッフルします。
  5. 弱点をシャッフルする
  6. ストロング配列の要素と同じ数のグループを準備し、各グループにストロングの 1 つ(要素がある場合はなし) を配置し、必要な数のウィークnullで完了します。
  7. グループごとにシャッフルする
  8. 前の関数の結果配列と同じように順序付けられた参加者を返します

そして対応するコード:

function splitStrongsAndWeaks($participants) {
    $strongs = array();
    $weaks = array();

    foreach($participants as $participant) {
        if($participant != null && $participant[1] == 1)
            $strongs[] = $participant;
        else
            $weaks[] = $participant;
    }

    return array($strongs, $weaks);
}

function insertNullValues($elements, $totalNeeded)
{
    $strongsNumber = count($elements);
    if($strongsNumber == $totalNeeded)
        return $elements;
    if($strongsNumber == 1)
    {
        if(mt_rand(0, 1))
            array_unshift($elements, null);
        else
            $elements[] = null;
        return $elements;
    }
    if($strongsNumber & 1)
        $half = ($strongsNumber >> 1) + mt_rand(0, 1);
    else
        $half = $strongsNumber >> 1;
    return array_merge(insertNullValues(array_splice($elements, 0, $half), $totalNeeded >> 1), insertNullValues($elements, $totalNeeded >> 1));
}

function shuffleParticipants($participants, $totalNeeded) {
    list($strongs, $weaks) = splitStrongsAndWeaks($participants);

    // If there are only weaks or a single strong, just shuffle them
    if(count($strongs) < 2) {
        shuffle($participants);
        $participants = insertNullValues($participants, $totalNeeded);
    }
    else {
        shuffle($strongs);

        // If there are more strongs, we need to put some with the weaks
        if(count($strongs) > $totalNeeded / 2) {
            list($strongs, $strongsToWeaks) = array_chunk($strongs, $totalNeeded / 2);
            $weaks = array_merge($weaks, $strongToWeaks);
            $neededGroups = $totalNeeded / 2;
        }
        // Else we need to make sure the number of groups will be a power of 2
        else {
            $neededGroups = 1 << ceil(log(count($strongs), 2));
            if(count($strongs) < $neededGroups)
                $strongs = insertNullValues($strongs, $neededGroups);
        }

        shuffle($weaks);

        // Computing needed non null values in each group
        $neededByGroup = $totalNeeded / $neededGroups;
        $neededNonNull = insertNullValues(array_fill(0, count($participants), 1), $totalNeeded);
        $neededNonNull = array_chunk($neededNonNull, $neededByGroup);
        $neededNonNull = array_map('array_sum', $neededNonNull);

        // Creating groups, putting 0 or 1 strong in each
        $participants = array();            
        foreach($strongs as $strong) {
            $group = array();

            if($strong != null)
                $group[] = $strong;
            $nonNull = array_shift($neededNonNull);
            while(count($group) < $nonNull)
                $group[] = array_shift($weaks);
            while(count($group) < $neededByGroup)
                $group[] = null;

            // Shuffling again each group so you can get for instance 1 -> weak, 17 -> strong
            shuffle($group);
            $participants[] = $group;
        }

        // Flattening to get a 1-dimension array
        $participants = call_user_func_array('array_merge', $participants);
    }

    // Returned array contains participants ordered the same way as getOrder()
    // (eg. with 32 participants, first will have number 1, second number 17 and so on...)
    return $participants;
}

結果の配列に括弧内の数字をインデックスとして持たせたい場合は、次のように簡単に実行できます。

$order = getOrder(count($participants));
$participants = array_combine($order, shuffleParticipants($participants, count($order)));
于 2013-09-02T20:53:05.413 に答える
1

この大ざっぱなコードは、あなたが望むものかもしれません:

<?php

class Pair
{
    public $a;
    public $b;

    function __construct($a, $b) {
        if(($a & 1) != ($b & 1)) 
            throw new Exception('Invalid Pair');
        $this->a = $a;
        $this->b = $b;
    }
}

class Competition
{
    public $odd_group = array();
    public $even_group = array();

    function __construct($order) {
        $n = 1 << $order;
        $odd = array();
        $even = array();
        for($i = 0; $i < $n; $i += 4) {
            $odd[] = $i + 1;
            $odd[] = $i + 3;
            $even[] = $i + 2;
            $even[] = $i + 4;
        }
        shuffle($odd);
        shuffle($even);
        for($i = 0; $i < count($odd); $i += 2) {
            $this->odd_group[] = new Pair($odd[$i], $odd[$i+1]);
            $this->even_group[] = new Pair($even[$i], $even[$i+1]);
        }
        echo "Odd\n";
        for($i = 0; $i < count($this->odd_group); ++$i) {
            $pair = $this->odd_group[$i]; 
            echo "{$pair->a} vs. {$pair->b}\n";
        }
        echo "Even\n";
        for($i = 0; $i < count($this->even_group); ++$i) {
            $pair = $this->even_group[$i]; 
            echo "{$pair->a} vs. {$pair->b}\n";
        }
    }
}

new Competition(5);

?>
于 2013-09-02T19:20:35.850 に答える