誰が行くの?手伝って頂けますか?

もしアベが行くなら、ベスとダイアナは行く。ベスが行くなら、キャサリンは行く。キャサリンが行くなら、ダイアナは行く。ダイアナが行くなら、エズラは行く。
3人しか行きません。誰が行くの?

チャレンジ

各ペアリングでは、第1の人が行く場合に第2の人が行き、行く人は正の整数であるように、いくつかのペアリングのリストが与えられると、誰が行くかの可能性を決定する。出力が一貫している限り、いずれかを出力することができます。

上記の例は、 [(A、B)、(A、D)、(B、C)、(C、D)、(D、E)]、3
視覚的にグラフとして表すことができる。

A -> B -> C -> D -> E
⤷-------------⤴ 

もしAが行くなら、誰もが行かなければならないので、少なくとも5人は行く.3人になることはできない。

Bが行くと、C、D、Eは行かなければならないので、少なくとも4人は行きます.3人になることはできません。

このようにして、C、D、Eを残して、 [C、D、E] の最終出力を得ます。

入力 [(0,1)、(0,3)、(1,2)、(2,3)、(3,4)]、3 は同じ状況を表し、 (出力
[2,3,4] を使用して)テストケースで与えられています。

私たちは、少なくとも1組のペアの人以外の人は考慮しないことを前提としています。たとえば、この例では 5
または F という人はいません。

I/O

あなたのプログラム/機能は、有向グラフを表すペアのリストである g と、行く人の数
n入力する必要があります。入力 g
は、追加情報をエンコードせず、少なくとも
人を考慮してエンコードすることができる形式(隣接行列など)で撮影することができます)。

また、 p 、人のリスト、および/または c
、考慮する人数を(オプションで)入力することもできます。 人々のリスト p
c 人数を取得するには、 g (ソート済み)
を入力します(末尾に
L を追加します)。

プログラム/関数は次の場合には処理する必要はありません。

  • 整数入力が考慮されている人数を超えています。
  • 整数入力が正でない
  • 繰り返しペアリング
  • 反射的なペアリング(例:(A、A)または(0,0)
  • 不可能な状況(例: [(A、B)、(B、A)]、1

出力は、1〜24人のリストを表すことができる任意の形式でなければなりません。

テストケース

テストケースの出力に OR がある場合、プログラムは
1つまたはすべての選択肢を返します。

[(0,1),(1,2),(2,3),(2,5),(5,6),(6,3),(6,7),(7,4)], 1 => [3] OR [4]
[(0,1),(1,2)], 1 => [2]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)], 1 => [7]
[(1,2),(2,3)], 2 => [2,3]
[(1,2),(3,4)], 2 => [1,2] OR [3,4] OR [2,4]
[(0,1),(1,2),(1,8),(2,3),(3,4),(4,11),(5,4),(5,6),(6,13),(13,20),(13,12),(12,19),(20,19),(4,19),(19,18),(11,10),(10,3),(10,2),(10,9),(9,8),(8,1),(8,7),(18,17),(18,24),(17,24),(24,23),(17,16),(16,23),(24,18),(16,15),(23,22),(22,15),(22,21),(21,14),(14,15)], 1 => [7] OR [15]
[(0,1),(1,0),(0,2),(1,3)], 1 => [2] OR [3]
[(0,1),(1,0),(0,2),(1,3)], 2 => [2,3]
[(0,1),(1,2)], 3 => [0,1,2]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 4 => [8,9,4,7]
[(0,1),(1,0),(0,2),(1,3)], 4 => [0,1,2,3]
[(0,1),(1,2),(2,3),(2,5),(5,6),(6,3),(6,7),(7,4)], 5 => [3,4,5,6,7]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 5 => [4,5,7,8,9]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)], 6 => [2,3,4,5,6,7]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)], 7 => [1,2,3,4,5,6,7]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 7 => [3,4,5,6,7,8,9]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 8 => [2,3,4,5,6,7,8,9]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 9 => [1,2,3,4,5,6,7,8,9]
[(0,1),(1,2),(1,8),(2,3),(3,4),(4,11),(5,4),(5,6),(6,13),(13,20),(13,12),(12,19),(20,19),(4,19),(19,18),(11,10),(10,3),(10,2),(10,9),(9,8),(8,1),(8,7),(18,17),(18,24),(17,24),(24,23),(17,16),(16,23),(24,18),(16,15),(23,22),(22,15),(22,21),(21,14),(14,15)], 9 => [14,15,16,17,18,21,22,23,24]
ベストアンサー

Husk, 14 10 bytes

~f`öΠFf†€Ṗ

Takes three inputs: number of people to go, 2-row matrix of the
constraints, and list of all people involved, in this order.
Returns all possible lists of people who go. If you want to output
only one list, replace the leftmost f by
. Try it
online!

説明

考え方は、 p のサブセット n をループし、 g
で指定した条件を満たすものを保持することです。ペアが行くと、第二の人も行く必要があります。

~f`öΠFf†€Ṗ  Implicit inputs, say n=3, g=[[1,3,3],[4,1,4]] and p=[1,2,3,4]
         Ṗ  All n-element subsets of p: [[1,2,3],[2,3,4],[1,3,4],[1,2,4]]
~f          Keep those subsets (say q=[1,2,4]) for which
  `ö        this function gives a truthy (nonzero) result:
       †     Deep map over g:
        €    index in q, or 0 if doesn't occur: [[1,0,0],[3,1,3]]
     Ff      Fold by select (filter second row by truthiness on first row): [3]
    Π        Product: 3

このプログラムは、プログラムの引数が正しい関数にどのように渡されるのかを説明するのが本当に難しいものの1つですが、試してみます。
最初に、 n が最初の引数なので、直接に渡すことができ、リストを取得してその
n -subsets。 次の2つの入力は gp
で、この時点でのプログラムの形状は〜(f)(
`öΠFf†€)(Ṗn)
を明瞭にするためにカッコが付いています。 演算子
g`` `結果を f
と組み合わせます。 Ṗnppn
サブセットに過ぎません。 g は実際には 2番目のですので、 g
は逆の順序で引数を取ります。この関数の引数。 最初の引数は、 f
(filter)で抽出されたṖnpの要素 q です。 q
のメンバシップをテストする関数となる q 、および
ディープ・マップ
>を2番目の引数 g に置き換えます。
次に、ΠFfが結果に適用されます。
öの役割はΠFf†を一つの関数にまとめて、
`〜f

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です