टूर्नामेंट ब्रैकेट प्लेसमेंट एल्गोरिदम

Question

प्रतिद्वंद्वी के बीज (उदाहरण के लिए बीज 1 से 16) की एक सूची को देखते हुए, मैं एक एल्गोरिदम लिखने की कोशिश कर रहा हूं जिसके परिणामस्वरूप शीर्ष बीज उस दौर में सबसे कम बीज खेल रहा है, दूसरा बीज खेल रहा है दूसरा सबसे निचला बीज, इत्यादि

"मैचों" में 1 और 16, 2 और 15 समूह समूह बनाना काफी आसान है, लेकिन मुझे यह सुनिश्चित करने की भी आवश्यकता है कि उच्चतर बीज अगले दौर में निचले बीज को खेलेंगे।

सही स्थान के साथ एक उदाहरण ब्रैकेट:

1 vs 16 
      1 vs 8 
8 vs 9 
         1 vs 4 
4 vs 13 
      4 vs 5 
5 vs 12 
            1 vs 2 
2 vs 15 
      2 vs 7 
7 vs 10 
         2 vs 3 
3 vs 14 
      3 vs 6 
6 vs 11

आप देख सकते हैं, बीज 1 और 2 ही फाइनल में मिलते हैं।

Answer 1

मैं निम्नलिखित एल्गोरिदम के साथ आया हूं। यह अति-कुशल नहीं हो सकता है, लेकिन मुझे नहीं लगता कि यह वास्तव में होना चाहिए। यह PHP में लिखा है।

<?php 
    $players = range(1, 32); 
    $count = count($players); 

    // Order players. 
    for ($i = 0; $i < log($count/2, 2); $i++) { 
     $out = array(); 

     foreach ($players as $player) { 
      $splice = pow(2, $i); 

      $out = array_merge($out, array_splice($players, 0, $splice)); 

      $out = array_merge($out, array_splice($players, -$splice)); 
     } 

     $players = $out; 
    } 

    // Print match list. 
    for ($i = 0; $i < $count; $i++) { 
     printf('%s vs %s<br />%s', $players[$i], $players[++$i], PHP_EOL); 
    } 
?> 

Answer 2

• हर दौर तरह टीमों पर बोने मापदंडों के आधार पर
• ith की स्थिति में टीम टीम के साथ एन-मैं + 1

Answer 3

अपनी मान्यताओं के साथ

, खिलाड़ियों निभाता है (यदि वहाँ एक दौर में टीमों n कर रहे हैं) फाइनल में 1 और 2 खेलेंगे, सेमीफाइनल में खिलाड़ियों को 1-4, क्वार्टर फाइनल में खिलाड़ियों को 1-8 और इसी तरह से, ताकि आप आकाश से प्रस्तावित फाइनल से टूर्नामेंट को पीछे से पीछे बना सकें। टूर्नामेंट के बारे में सोचें कि एक पेड़ जिसका रूट अंतिम है।

रूट नोड में, आपके खिलाड़ी {1, 2} हैं।

पेड़ को अगले स्तर तक फिर से विस्तारित करने के लिए, पेड़ में नीचे की परत पर सभी नोड्स लें, एक-एक करके, और प्रत्येक के लिए दो बच्चे बनाएं, और मूल नोड के खिलाड़ियों में से प्रत्येक को रखें बनाए गए बच्चे नोड्स में से एक। फिर खिलाड़ियों की अगली परत जोड़ें और उन्हें गेम में मैप करें ताकि सबसे खराब जोड़ा गया खिलाड़ी सर्वश्रेष्ठ प्री-मौजूदा प्लेयर के खिलाफ खेल सके और इसी तरह।

एल्गोरिथ्म के यहां पहले दौर:

{1,2} --- create next layer 

     {1, _} 
    /  --- now fill the empty slots 
{1,2} 
     \{2, _} 

     {1, 4} --- the slots filled in reverse order 
    /  
{1,2} 
     \{2, 3} --- create next layer again 


      /{1, _} 
     {1, 4} 
    / \{4, _} 
{1,2}     --- again fill 
     \  /{2, _} 
     {2, 3} 
      \{3, _} 

      /{1, 8} 
     {1, 4} 
    / \{4, 5} --- ... and so on 
{1,2} 
     \  /{2, 7} 
     {2, 3} 
      \{3, 6} 

आप देख सकते हैं, यह एक ही पेड़ तुम्हें तैनात पैदा करता है।

Answer 4

यह जावा स्क्रिप्ट एक सरणी जहां प्रत्येक भी सूचकांक अगले अजीब सूचकांक

function seeding(numPlayers){ 
    var rounds = Math.log(numPlayers)/Math.log(2)-1; 
    var pls = [1,2]; 
    for(var i=0;i<rounds;i++){ 
    pls = nextLayer(pls); 
    } 
    return pls; 
    function nextLayer(pls){ 
    var out=[]; 
    var length = pls.length*2+1; 
    pls.forEach(function(d){ 
     out.push(d); 
     out.push(length-d); 
    }); 
    return out; 
    } 
} 

> seeding(2) 
[1, 2] 
> seeding(4) 
[1, 4, 2, 3] 
> seeding(8) 
[1, 8, 4, 5, 2, 7, 3, 6] 
> seeding(16) 
[1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11] 

Answer 5

# Here's one in python - it uses nested list comprehension to be succinct: 

from math import log, ceil 

def seed(n): 
    """ returns list of n in standard tournament seed order 

    Note that n need not be a power of 2 - 'byes' are returned as zero 
    """ 

    ol = [1] 

    for i in range(ceil(log(n)/log(2))): 

     l = 2*len(ol) + 1 

     ol = [e if e <= n else 0 for s in [[el, l-el] for el in ol] for e in s] 

    return ol 

Answer 6

इस कब से इस विषय पर खोज कर आता है निभाता है देता है, और यह एक और जवाब यह है कि हल खोजने के लिए निराशाजनक है समस्या और बीज को "सुंदर" क्रम में रखता है, मैं darkangel से PHP कोड का अपना संस्करण जोड़ दूंगा। मैंने उच्च बीज खिलाड़ियों को अलविदा देने की संभावना भी जोड़ा।

यह ओओ पर्यावरण में कोडित किया गया था, इसलिए प्रतिभागियों की संख्या $-> फाइनल में है और बाई की संख्या इस-> बाईस में है। मैंने केवल अलविदा के बिना और दो बाई के साथ कोड का परीक्षण किया है।

public function getBracket() { 
     $players = range(1, $this->finalists); 
     for ($i = 0; $i < log($this->finalists/2, 2); $i++) { 
     $out = array(); 
     $reverse = false; 
     foreach ($players as $player) { 
      $splice = pow(2, $i); 
      if ($reverse) { 
      $out = array_merge($out, array_splice($players, -$splice)); 
      $out = array_merge($out, array_splice($players, 0, $splice)); 
      $reverse = false; 
      } else { 
      $out = array_merge($out, array_splice($players, 0, $splice)); 
      $out = array_merge($out, array_splice($players, -$splice)); 
      $reverse = true; 
      } 
     } 
     $players = $out; 
     } 
     if ($this->byes) { 
     for ($i = 0; $i < $this->byes; $i++) { 
      for ($j = (($this->finalists/pow(2, $i)) - 1); $j > 0; $j--) { 
      $newPlace = ($this->finalists/pow(2, $i)) - 1; 
      if ($players[$j] > ($this->finalists/(pow(2 ,($i + 1))))) { 
       $player = $players[$j]; 
       unset($players[$j]); 
       array_splice($players, $newPlace, 0, $player); 
      } 
      } 
     } 
     for ($i = 0; $i < $this->finalists/(pow(2, $this->byes)); $i++) { 
      $swap[] = $players[$i]; 
     } 
     for ($i = 0; $i < $this->finalists /(pow(2, $this->byes)); $i++) { 
      $players[$i] = $swap[count($swap) - 1 - $i]; 
     } 
     return array_reverse($players); 
     } 
     return $players; 
    } 

Answer 7

जावास्क्रिप्ट कोड के लिए, नीचे दिए गए दो कार्यों में से एक का उपयोग करें। पूर्व अवशोषक शैली & बहुत तेज है। उत्तरार्द्ध & नीदरर रिकर्सिव है, लेकिन अपेक्षाकृत छोटी संख्या में टीमों (< 16384) पर लागू होता है।

यहां आप पहले से ही कब्जे वाले लोगों को मिरर करके एक-एक करके स्पॉट भरते हैं। उदाहरण के लिए, पहली बीज वाली टीम (वह संख्या 0 है) शीर्ष स्थान पर जाती है। दूसरा एक (1) ब्रैकेट के दूसरे भाग में विपरीत स्थान पर है। तीसरी टीम (2) दर्पण 1 ब्रैकेट & के आधे हिस्से में दर्पण। नेस्टेड लूप के बावजूद, एल्गोरिदम में टीमों की संख्या के आधार पर एक रैखिक समय जटिलता होती है।

// functional style 
const foo = n => 
    n === 1 ? [0] : foo(n >> 1).reduce((p, c) => [...p, c, n - c - 1], []) 

मूल रूप से, आप पिछले समारोह में के रूप में ही मिरर करते हैं, लेकिन रिकर्सिवली:

• n = 1 टीम के लिए, यह सिर्फ [0] है

  यहाँ पुनरावर्ती विधि है।

• n = 2 के लिए टीमों, आप तर्क n-1 को यह समारोह लागू (अर्थात, 1 है) & [0] मिलता है। फिर आप भी स्थिति में दर्पण तत्वों को उनके द्वारा तत्वों को डालने से सरणी को दोगुना करते हैं। इस प्रकार, [0][0, 1] बन जाता है।

• n = 4 टीमों के लिए, आप एक ही ऑपरेशन करते हैं, इसलिए [0, 1][0, 3, 1, 2] बन जाता है।

आप, मानव पठनीय आउटपुट प्राप्त एक करके परिणामी सरणी के प्रत्येक तत्व में वृद्धि करना चाहते हैं:

const readableArr = arr.map(i => i + 1) 

Answer 8

मैं भी एक समाधान PHP में लिखा लिखा था। मैंने पेट्रिक बोडिन के जवाब को देखा, लेकिन सोचा कि एक आसान तरीका होना चाहिए।

यह क्या करता है जो अंधेरे ने पूछा: यह सभी बीजों सही स्थिति में देता है। मैच उनके उदाहरण के समान हैं, लेकिन प्रीटीयर ऑर्डर में, बीज 1 और बीज संख्या 16 स्कीमा के बाहर हैं (जैसा कि आप टेनिस टूर्नामेंट में देखते हैं)।

यदि कोई परेशान नहीं है (जिसका मतलब है कि उच्च बीज वाले खिलाड़ी हमेशा निचले बीज वाले खिलाड़ी से जीतते हैं), तो आप फाइनल में बीज 1 बनाम बीज 2 के साथ समाप्त हो जाएंगे।

यह वास्तव में दो परिणाम होते हैं अधिक:

1. यह सही क्रम

2. यह सही स्थिति में बाई में भर जाता है ((जो सही स्थिति में बाई डालने के लिए एक आवश्यकता है) से पता चलता यदि आवश्यक हो तो)

क्या एक भी उन्मूलन ब्रैकेट की तरह दिखना चाहिए के बारे में एक सही स्पष्टीकरण: http://blog.playdriven.com/2011/articles/the-not-so-simple-single-elimination-advantage-seeding/

16 प्रतिभागियों के लिए

कोड उदाहरण:

<?php 

define('NUMBER_OF_PARTICIPANTS', 16); 

$participants = range(1,NUMBER_OF_PARTICIPANTS); 
$bracket = getBracket($participants); 
var_dump($bracket); 

function getBracket($participants) 
{ 
    $participantsCount = count($participants); 
    $rounds = ceil(log($participantsCount)/log(2)); 
    $bracketSize = pow(2, $rounds); 
    $requiredByes = $bracketSize - $participantsCount; 

    echo sprintf('Number of participants: %d<br/>%s', $participantsCount, PHP_EOL); 
    echo sprintf('Number of rounds: %d<br/>%s', $rounds, PHP_EOL); 
    echo sprintf('Bracket size: %d<br/>%s', $bracketSize, PHP_EOL); 
    echo sprintf('Required number of byes: %d<br/>%s', $requiredByes, PHP_EOL);  

    if($participantsCount < 2) 
    { 
     return array(); 
    } 

    $matches = array(array(1,2)); 

    for($round=1; $round < $rounds; $round++) 
    { 
     $roundMatches = array(); 
     $sum = pow(2, $round + 1) + 1; 
     foreach($matches as $match) 
     { 
      $home = changeIntoBye($match[0], $participantsCount); 
      $away = changeIntoBye($sum - $match[0], $participantsCount); 
      $roundMatches[] = array($home, $away); 
      $home = changeIntoBye($sum - $match[1], $participantsCount); 
      $away = changeIntoBye($match[1], $participantsCount); 
      $roundMatches[] = array($home, $away); 
     } 
     $matches = $roundMatches; 
    } 

    return $matches; 

} 

function changeIntoBye($seed, $participantsCount) 
{ 
    //return $seed <= $participantsCount ? $seed : sprintf('%d (= bye)', $seed); 
    return $seed <= $participantsCount ? $seed : null; 
} 

?> 

उत्पादन:

Number of participants: 16 
Number of rounds: 4 
Bracket size: 16 
Required number of byes: 0 
C:\projects\draw\draw.php:7: 
array (size=8) 
    0 => 
    array (size=2) 
     0 => int 1 
     1 => int 16 
    1 => 
    array (size=2) 
     0 => int 9 
     1 => int 8 
    2 => 
    array (size=2) 
     0 => int 5 
     1 => int 12 
    3 => 
    array (size=2) 
     0 => int 13 
     1 => int 4 
    4 => 
    array (size=2) 
     0 => int 3 
     1 => int 14 
    5 => 
    array (size=2) 
     0 => int 11 
     1 => int 6 
    6 => 
    array (size=2) 
     0 => int 7 
     1 => int 10 
    7 => 
    array (size=2) 
     0 => int 15 
     1 => int 2 

आप बदलना 16 6 में मिलता है:

Number of participants: 6 
Number of rounds: 3 
Bracket size: 8 
Required number of byes: 2 
C:\projects\draw\draw.php:7: 
array (size=4) 
    0 => 
    array (size=2) 
     0 => int 1 
     1 => null 
    1 => 
    array (size=2) 
     0 => int 5 
     1 => int 4 
    2 => 
    array (size=2) 
     0 => int 3 
     1 => int 6 
    3 => 
    array (size=2) 
     0 => null 
     1 => int 2 

Answer 9

मैं एक PHP/Laravel पर काम किया प्लगइन जो प्रारंभिक दौर रॉबिन के साथ/बिना ब्रैकेट उत्पन्न करता है। शायद यह आपके लिए उपयोगी हो सकता है, मुझे नहीं पता कि आप किस तकनीक का उपयोग कर रहे हैं। यहां जिथब है।

https://github.com/xoco70/kendo-tournaments

आशा है कि यह मदद करता है!

Answer 10

ए सी संस्करण।

int * pctournamentSeedArray(int PlayerCnt) 
{ 
    int * Array; 
    int * PrevArray; 
    int i; 

    Array = meAlloc(sizeof(int) * PlayerCnt); 

    if (PlayerCnt == 2) 
    { 
     Array[0] = 0; 
     Array[1] = 1; 
     return Array; 
    } 

    PrevArray = pctournamentSeedArray(PlayerCnt/2); 
    for (i = 0; i < PlayerCnt;i += 2) 
    { 
     Array[i] = PrevArray[i/2]; 
     Array[i + 1] = (PlayerCnt - 1) - Array[i] ; 
    } 
    meFree(PrevArray); 
    return Array; 
}