Algorithms

' Randomly assign remaining entries to the current column
rndEntries = TotalEntries - curEntries

public struct ForbiddenConnection
{
    private readonly int _source;
    private readonly int[] _destination;
    
    private ForbiddenConnection(int source, int[] destination)
    {
        _source = source;
        _destination = destination;
    }
    
    public static ForbiddenConnection Create(int source, IEnumerable<int> destination)
    {
        return new ForbiddenConnection(source, SortedDistinct(destination).ToArray());
    }
    
    public static ForbiddenConnection Create(int source, params int[] destination)
    {
        return Create(source, destination.AsEnumerable());
    }
    
    private static IEnumerable<int> SortedDistinct(IEnumerable<int> source)
    {
        if (source == null) yield break;
        
        bool started = false;
        int lastItem = 0;
        foreach (int item in source.OrderBy(x => x))
        {
            if (started && item == lastItem) continue;
            
            yield return item;
            lastItem = item;
            started = true;
        }
    }
    
    public int Source
    {
        get { return _source; }
    }
    
    public bool Contains(int destination)
    {
        return _destination != null && Array.BinarySearch(_destination, destination) >= 0;
    }
}

public sealed class GraphGenerator : IEnumerable<IReadOnlyList<int>>
{
    private readonly int _length;
    private readonly IDictionary<int, ForbiddenConnection> _forbidden;
    
    private GraphGenerator(int length, IEnumerable<ForbiddenConnection> forbidden)
    {
        _length = length;
        
        if (forbidden != null)
        {
            _forbidden = forbidden.ToDictionary(fc => fc.Source);
        }
        else
        {
            _forbidden = new Dictionary<int, ForbiddenConnection>(0);
        }
    }
    
    public static GraphGenerator Create(int length, IEnumerable<ForbiddenConnection> forbidden)
    {
        if (length < 2) throw new ArgumentOutOfRangeException("length");
        return new GraphGenerator(length, forbidden);
    }
    
    public static GraphGenerator Create(int length, params ForbiddenConnection[] forbidden)
    {
        return Create(length, forbidden.AsEnumerable());
    }
    
    private bool Validate(IReadOnlyList<int> graph)
    {
        Debug.Assert(graph != null);
        Debug.Assert(graph.Count == _length);
        
        for (int i = 0; i < graph.Count; i++)
        {
            int index = graph[i];
            Debug.Assert(0 <= index && index < _length);
            
            if (index == i)
            {
                Trace.TraceInformation("Node {0} points to itself.", i);
                return false;
            }
            
            ForbiddenConnection forbidden;
            if (_forbidden.TryGetValue(i, out forbidden) && forbidden.Contains(index))
            {
                Trace.TraceInformation("Node {0} cannot point to node {1}.", i, index);
                return false;
            }
            
            for (int j = i + 1; j < graph.Count; j++)
            {
                if (graph[j] == index)
                {
                    Trace.TraceInformation("Nodes {0} and {1} both point to node {2}.", i, j, index);
                    return false;
                }
            }
        }
        
        return true;
    }
    
    public IEnumerator<IReadOnlyList<int>> GetEnumerator()
    {
        // TODO: Return every valid permutation.
    }
    
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

public struct Permutation : IReadOnlyList<int>
{
    public static readonly Permutation Empty = default(Permutation);
    
    private readonly int[] _value;
    
    private Permutation(Permutation source, int index, int value)
    {
        if (source.Count == 0)
        {
            _value = new[] { value };
        }
        else
        {
            _value = new int[source.Count + 1];
            _value[index] = value;
            
            if (index != 0) 
            {
                Array.Copy(source._value, 0, _value, 0, index);
            }
            if (index != source.Count)
            {
                Array.Copy(source._value, index, _value, index + 1, source.Count - index);
            }
        }
    }
    
    public int Count
    {
        get { return (_value == null) ? 0 : _value.Length; }
    }
    
    public int this[int index]
    {
        get
        {
            if (0 > index || index >= Count) throw new ArgumentOutOfRangeException("index");
            return _value[index];
        }
    }
    
    public IEnumerator<int> GetEnumerator()
    {
        if (_value == null) return Enumerable.Empty<int>().GetEnumerator();
        return _value.AsEnumerable().GetEnumerator();
    }
    
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    
    public static IEnumerable<Permutation> HamiltonianPermutations(int ofSize)
    {
        if (ofSize < 0) throw new ArgumentOutOfRangeException("ofSize");
        return HamiltonianPermutationsIterator(ofSize);
    }
    
    private static IEnumerable<Permutation> HamiltonianPermutationsIterator(int ofSize)
    {
        if (ofSize == 0)
        {
            yield return Empty;
            yield break;
        }
        
        bool forwards = false;
        foreach (var permutation in HamiltonianPermutationsIterator(ofSize - 1))
        {
            for (int index = 0; index < ofSize; index++)
            {
                int insertAt = forwards ? index : ofSize - index - 1;
                yield return new Permutation(permutation, insertAt, ofSize - 1);
            }
            
            forwards = !forwards;
        }
    }
}

public IEnumerator<IReadOnlyList<int>> GetEnumerator()
{
    return Permutation.HamiltonianPermutations(_length)
        .Cast<IReadOnlyList<int>>()
        .Where(Validate)
        .GetEnumerator();
}

var generator = GraphGenerator.Create(8,
    ForbiddenConnection.Create(0, 1), // Person A cannot point to person B
    ForbiddenConnection.Create(1, 0)  // Person B cannot point to person A
);

if (!generator.Any())
{
    // Configuration is not possible
}