0
$\begingroup$

Suppose I have an alphabetized list of n people, and I want to choose k from the list such that any two people are at least g away from each other on the list

(E.g if g=2, then none of the k people are next to each other on the list).

Is there a formula / general way to solve these types of problems, for any k,n, and g?

1 Answers 1

1

The problem has a solution only if \ceiling$(n/g)>=k$.

Form a directed graph with each of the $n$ people a ode. Put a directed edge $(u,v)$ whenever $v$ is at least $g$ positions after $u$ in the dictionary. Run a graph traversal algorithm starting at each one of the first $g$ nodes. Each resulting path with length $k-1$ is an answer.

  • 0
    Yw, Glad it helped. I don't think there is. It is a recursive solution. The algorithm would be the solution "formula" itself. There is a lengthy closed form for its count though and I haven't figured it-- yet.2012-12-13