Who's Going? Can you help me?

Question

If Abe goes, then Beth and Diana go. If Beth goes, then Catherine goes. If Catherine goes, then Diana goes. If Diana goes, then Ezra goes. Only three people go. Who goes?

Challenge

Given a list of several pairings of people, such that in each pairing the second person goes if the first person goes, and a positive integer number of people who go, determine one or all possibilities of who goes. You may output either, as long as the output is consistent.

The example above may be represented in input by [(A,B),(A,D),(B,C),(C,D),(D,E)],3, which can be represented as a graph visually as:

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

If A goes, then everyone must go, so at least 5 people go, which cannot be 3 people.

If B goes, then C, D, and E must go, so at least 4 people go, which cannot be 3 people.

Thus we are left with C, D, and E going, yielding a final output of [C,D,E].

The input [(0,1),(0,3),(1,2),(2,3),(3,4)],3 represents the same situation and is the format given in the test cases (with output [2,3,4]).

We assume that no people other than the people in at least one pairing should be considered. For example, there is no person 5 or F in this example.

I/O

Your program/function must input g, the list of pairings which represents a directed graph, and n, the number of people who will go. Input g may be taken in any format (such as an adjacency matrix) which does not encode additional information and can encode at least 25 people to consider (the example considered 5 people).

You may also (optionally) input p, the list of people, and/or c, the number of people to consider. List of people p given g (sorted). (append L to end to get number of people c).

Your program/function does not have to handle if:

• the integer input is greater than the number of people considered.
• the integer input is not positive
• repeat pairings
• reflexive pairings (e.g. (A,A) or (0,0))
• impossible situations (e.g. [(A,B),(B,A)],1)

The output should be in any format which can represent a list from 1 to 24 people.

Test Cases

If the output of a test case has an OR in it, your program may return any one or all of the choices.

[(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]

Answer 1

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!

Explanation

The idea is to loop over the size-n subsets of p and keep those that satisfy the condition imposed by g: if the first person in a pair goes, then the second person must go too.

~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

This program is one of those where it's really hard to explain how the program arguments are passed to the correct functions, but I'll try. First, n is the first argument, so it can be given to Ṗ directly, making it a function that takes a list and returns its n-subsets. The next two inputs are g and p, and the program's shape at this point is ~(f)(`öΠFf†€)(Ṗn) with parentheses added for clarity. The operator ~ gives g to `öΠFf†€ and p to Ṗn, and combines the results with f. Ṗnp is just the n-subsets of p, so that's simple. The operator ` causes öΠFf†€ to take its arguments in the reverse order, so g is actually the second argument of this function. The first argument is an element q of Ṗnp, which is extracted by f (filter). We give q as an argument to €, which becomes a function for testing membership in q, and deep map that over the second argument, which is g. Then ΠFf are applied to the result. The role of ö is just to compose ΠFf†€ into one function, which we can then pass on to ` and ~f.

Answer 2

Python 2, 100 98 bytes

g,n=input()
v=k=0
while bin(v).count("1")^n:k=v=k+1;exec"for a,b in g:v|=(v>>a&1)<<b\n"*25
print v

I assume that the people are numbered from 0 to n. g is a list of pairs just like in the question. The output is a number where the ith bit is set if the ith person goes.

Answer 3

Wolfram Language (Mathematica), 62 55 bytes

Select[g=#;#2~Subsets~{#3},#==g~VertexOutComponent~#&]&

Try it online!

I/O

Takes as input the following three arguments:

• list of she-goes-I-go pairs, as rules (x->y). The first example in the question would be encoded as {A->B,A->D,B->C,C->D,D->E}. Can also take a Mathematica Graph object.
• list of people involved. E.g., {A,B,C,D,E}.
• number of people we want to go. E.g., 3.

The output is a list of all subsets of people of the right size who could go.

How it works

The older version was fancier, and contained the expression #|##&@@# which I'm very proud of, but this one just uses a built-in. VertexOutComponent computes the set of everyone else who must go, given a group of people who are going; we just Select the Subsets of the given size whose VertexOutcomponent is the same set and no bigger.

-7 bytes: the built-in.

Answer 4

Python 3, 97 95 bytes

lambda g,n,c:[k for k in range(2**c)if-1<bin(k).count("1")-n<all(k>>s&1for f,s in g if k>>f&1)]

Try it online!

Takes g as a list of pairs, as in the question, and additionally takes the number of people c. Returns all solutions in form n where bit i of n corresponds to whether or not person i attends.