総当たり戦の日程作成 in Smalltalk DouKaku?

総当たり戦の日程作成

任意の偶数Nのチームの総当たり戦を最短日数（N-1日）で行う場合の日程表を１つ作成してください。

解はひとつではない場合もあります。
もし、余力があれば、全ての可能性も求めてください。

これは、スポーツスケジューリングと言う分野の問題で、数学的には、カークマンの問題と言うのが近いようです。

例えば、４チームであれば、

1-2 3-4
1-3 2-4
1-4 2-3

６チームであれば

1-2 3-4 5-6 
1-3 2-5 4-6 
1-4 2-6 3-5 
1-5 2-4 3-6 
1-6 2-3 4-5

が解のひとつです。

see: カークマンの組分け

post comment

Posted feedbacks - Smalltalk

Squeak Smalltalk で。

| チーム数 全試合 待ち行列 全結果 |
チーム数 := 6.
全試合 := OrderedCollection new.
(1 to: チーム数) combinations: 2 atATimeDo: [:対戦ペア | 全試合 add: 対戦ペア copy].
待ち行列 := OrderedCollection with: {Set new. Set new. 1 to: チーム数. 全試合}.
全結果 := Set new.
[待ち行列 notEmpty] whileTrue: [
    | 分岐点 |
    分岐点 := 待ち行列 removeFirst.
    分岐点 third
        ifEmpty: [待ち行列 add: {分岐点 first, {分岐点 second}. Set new. 1 to: チーム数. 分岐点 last}] 
        ifNotEmpty: [
            分岐点 last ifEmpty: [全結果 add: 分岐点 first] ifNotEmpty: [
                分岐点 second
                    ifEmpty: [
                        | next |
                        next := 分岐点 last detect: [:each | 分岐点 third includesAllOf: each].
                        待ち行列 add: {
                            分岐点 first.
                            Set with: next.
                            分岐点 third copyWithoutAll: next.
                            分岐点 last copyWithout: next}]
                    ifNotEmpty: [
                        (分岐点 last reject: [:対戦 |
                                分岐点 second anySatisfy: [:確定分 |
                                    対戦 includesAnyOf: 確定分]]) do: [:次の試合 |
                            待ち行列 add: {
                                分岐点 first.
                                分岐点 second copyWith: 次の試合.
                                分岐点 third copyWithoutAll: 次の試合.
                                分岐点 last copyWithout: 次の試合}]]]]].
^全結果 asArray collect: [:リーグ |
    リーグ asArray collect: [:日程 |
        日程 asArray collect: [:対戦ペア | 対戦ペア first @ 対戦ペア second]]]

"=> {
{{1@2. 4@5. 3@6}. {2@6. 1@4. 3@5}. {2@3. 1@5. 4@6}. {2@5. 1@6. 3@4}. {2@4. 1@3. 5@6}}. 
{{2@6. 1@4. 3@5}. {2@4. 1@5. 3@6}. {2@3. 1@6. 4@5}. {2@5. 1@3. 4@6}. {1@2. 5@6. 3@4}}. 
{{1@2. 5@6. 3@4}. {2@3. 1@5. 4@6}. {2@6. 1@3. 4@5}. {2@4. 1@6. 3@5}. {2@5. 1@4. 3@6}}. 
{{1@2. 4@6. 3@5}. {2@6. 1@5. 3@4}. {2@4. 1@3. 5@6}. {2@3. 1@6. 4@5}. {2@5. 1@4. 3@6}}. 
{{1@2. 4@6. 3@5}. {2@4. 1@5. 3@6}. {2@6. 1@3. 4@5}. {2@3. 1@4. 5@6}. {2@5. 1@6. 3@4}}. 
{{1@2. 4@5. 3@6}. {2@3. 1@4. 5@6}. {2@6. 1@5. 3@4}. {2@5. 1@3. 4@6}. {2@4. 1@6. 3@5}}} "

DouKaku?

総当たり戦の日程作成

Posted feedbacks - Smalltalk

Index

Feed

Other

Link

Pathtraq