c - Langford 序列实现 Haskell 或 C

Question

在组合数学中，一个 Langford pairing ，也称为 Langford 序列，是 2n 数字序列 1, 1, 2, 2, ..., n,n 的排列，其中两个相距一个单位，两个二相距两个单位，更一般地，每个数字 k 的两个副本相距 k 个单位。

例如:

n = 3 的 Langford 配对由序列 2,3,1,2,1,3 给出。

• 在 haskell 或 C 中解决这个问题的好方法是什么
• 你能推荐一个算法来解决它吗(不想使用蛮力)？

------------------------编辑---------------- -----
我们如何定义将@Rafe 的代码放入 haskell 的数学规则

Answer 1

你想找到变量 {p1, p2, ..., pn} 的赋值(其中 pi 是 'i' 第一次出现的位置)，每个 pi 具有以下约束条件:

• pi 在 1..(1+n-i)
• if pi = k then forall pj where j != i
• pj != k
• pj != k + i
• pj != k - j
• pj != k + i - j

您需要一个明智的搜索策略。一个好的选择是在每个选择点选择具有最小剩余可能值集的 pi。

干杯!

[编辑:第二个附录。]

这是我最初编写的命令式版本的“主要功能”版本(请参阅下面的第一个附录)。从与搜索树中每个顶点关联的状态独立于所有其他状态的意义上说，它主要是功能性的，因此不需要那种踪迹或机器。但是，我使用命令式代码从父域集的副本中构建每个新域集。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MostlyFunctionalLangford
{
    class Program
    {
        // An (effectively functional) program to compute Langford sequences.
        static void Main(string[] args)
        {
            var n = 7;
            var DInit = InitLangford(n);
            var DSoln = Search(DInit);
            if (DSoln != null)
            {
                Console.WriteLine();
                Console.WriteLine("Solution for n = {0}:", n);
                WriteSolution(DSoln);
            }
            else
            {
                Console.WriteLine();
                Console.WriteLine("No solution for n = {0}.", n);
            }
            Console.Read();
        }

        // The largest integer in the Langford sequence we are looking for.
        // [I could infer N from the size of the domain array, but this is neater.]
        static int N;

        // ---- Integer domain manipulation. ----

        // Find the least bit in a domain; return 0 if the domain is empty.
        private static long LeastBitInDomain(long d)
        {
            return d & ~(d - 1);
        }

        // Remove a bit from a domain.
        private static long RemoveBitFromDomain(long d, long b)
        {
            return d & ~b;
        }

        private static bool DomainIsEmpty(long d)
        {
            return d == 0;
        }

        private static bool DomainIsSingleton(long d)
        {
            return (d == LeastBitInDomain(d));
        }

        // Return the size of a domain.
        private static int DomainSize(long d)
        {
            var size = 0;
            while (!DomainIsEmpty(d))
            {
                d = RemoveBitFromDomain(d, LeastBitInDomain(d));
                size++;
            }
            return size;
        }

        // Find the k with the smallest non-singleton domain D[k].
        // Returns zero if none exists.
        private static int SmallestUndecidedDomainIndex(long[] D)
        {
            var bestK = 0;
            var bestKSize = int.MaxValue;
            for (var k = 1; k <= N && 2 < bestKSize; k++)
            {
                var kSize = DomainSize(D[k]);
                if (2 <= kSize && kSize < bestKSize)
                {
                    bestK = k;
                    bestKSize = kSize;
                }
            }
            return bestK;
        }

        // Obtain a copy of a domain.
        private static long[] CopyOfDomain(long[] D)
        {
            var DCopy = new long[N + 1];
            for (var i = 1; i <= N; i++) DCopy[i] = D[i];
            return DCopy;
        }

        // Destructively prune a domain by setting D[k] = {b}.
        // Returns false iff this exhausts some domain.
        private static bool Prune(long[] D, int k, long b)
        {
            for (var j = 1; j <= N; j++)
            {
                if (j == k)
                {
                    D[j] = b;
                }
                else
                {
                    var dj = D[j];
                    dj = RemoveBitFromDomain(dj, b);
                    dj = RemoveBitFromDomain(dj, b << (k + 1));
                    dj = RemoveBitFromDomain(dj, b >> (j + 1));
                    dj = RemoveBitFromDomain(dj, (b << (k + 1)) >> (j + 1));
                    if (DomainIsEmpty(dj)) return false;
                    if (dj != D[j] && DomainIsSingleton(dj) && !Prune(D, j, dj)) return false;
                }
            }
            return true;
        }

        // Search for a solution from a given set of domains.
        // Returns the solution domain on success.
        // Returns null on failure.
        private static long[] Search(long[] D)
        {
            var k = SmallestUndecidedDomainIndex(D);
            if (k == 0) return D;

            // Branch on k, trying each possible assignment.
            var dk = D[k];
            while (!DomainIsEmpty(dk))
            {
                var b = LeastBitInDomain(dk);
                dk = RemoveBitFromDomain(dk, b);
                var DKeqB = CopyOfDomain(D);
                if (Prune(DKeqB, k, b))
                {
                    var DSoln = Search(DKeqB);
                    if (DSoln != null) return DSoln;
                }
            }

            // Search failed.
            return null;
        }

        // Set up the problem.
        private static long[] InitLangford(int n)
        {
            N = n;
            var D = new long[N + 1];
            var bs = (1L << (N + N - 1)) - 1;
            for (var k = 1; k <= N; k++)
            {
                D[k] = bs & ~1;
                bs >>= 1;
            }
            return D;
        }

        // Print out a solution.
        private static void WriteSolution(long[] D)
        {
            var l = new int[N + N + 1];
            for (var k = 1; k <= N; k++)
            {
                for (var i = 1; i <= N + N; i++)
                {
                    if (D[k] == 1L << i)
                    {
                        l[i] = k;
                        l[i + k + 1] = k;
                    }
                }
            }
            for (var i = 1; i < l.Length; i++)
            {
                Console.Write("{0} ", l[i]);
            }
            Console.WriteLine();
        }
    }
}

[编辑:第一个附录。]

我决定编写一个 C# 程序来解决 Langford 问题。它运行非常快，直到 n = 16，但此后您需要将其更改为使用 long，因为它将域表示为位模式。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Langford
{
    // Compute Langford sequences.  A Langford sequence L(n) is a permutation of [1, 1, 2, 2, ..., n, n] such
    // that the pair of 1s is separated by 1 place, the pair of 2s is separated by 2 places, and so forth.
    //
    class Program
    {
        static void Main(string[] args)
        {
            var n = 16;
            InitLangford(n);
            WriteDomains();
            if (FindSolution())
            {
                Console.WriteLine();
                Console.WriteLine("Solution for n = {0}:", n);
                WriteDomains();
            }
            else
            {
                Console.WriteLine();
                Console.WriteLine("No solution for n = {0}.", n);
            }
            Console.Read();
        }

        // The n in L(n).
        private static int N;

        // D[k] is the set of unexcluded possible positions in the solution of the first k for each pair of ks.
        // Each domain is represented as a bit pattern, where bit i is set iff i is in D[k].
        private static int[] D;

        // The trail records domain changes to undo on backtracking.  T[2k] gives the element in D to undo;
        // T[2k+1] gives the value to which it must be restored.
        private static List<int> T = new List<int> { };

        // This is the index of the next unused entry in the trail.
        private static int TTop;

        // Extend the trail to restore D[k] on backtracking.
        private static void TrailDomainValue(int k)
        {
            if (TTop == T.Count)
            {
                T.Add(0);
                T.Add(0);
            }
            T[TTop++] = k;
            T[TTop++] = D[k];
        }

        // Undo the trail to some earlier point.
        private static void UntrailTo(int checkPoint)
        {
            //Console.WriteLine("Backtracking...");

            while (TTop != checkPoint)
            {
                var d = T[--TTop];
                var k = T[--TTop];
                D[k] = d;
            }
        }

        // Find the least bit in a domain; return 0 if the domain is empty.
        private static int LeastBitInDomain(int d)
        {
            return d & ~(d - 1);
        }

        // Remove a bit from a domain.
        private static int RemoveBitFromDomain(int d, int b)
        {
            return d & ~b;
        }

        private static bool DomainIsEmpty(int d)
        {
            return d == 0;
        }

        private static bool DomainIsSingleton(int d)
        {
            return (d == LeastBitInDomain(d));
        }

        // Return the size of a domain.
        private static int DomainSize(int d)
        {
            var size = 0;
            while (!DomainIsEmpty(d))
            {
                d = RemoveBitFromDomain(d, LeastBitInDomain(d));
                size++;
            }
            return size;
        }

        // Find the k with the smallest non-singleton domain D[k].
        // Returns zero if none exists.
        private static int SmallestUndecidedDomainIndex()
        {
            var bestK = 0;
            var bestKSize = int.MaxValue;
            for (var k = 1; k <= N && 2 < bestKSize; k++)
            {
                var kSize = DomainSize(D[k]);
                if (2 <= kSize && kSize < bestKSize)
                {
                    bestK = k;
                    bestKSize = kSize;
                }
            }
            return bestK;
        }

        // Prune the other domains when domain k is reduced to a singleton.
        // Return false iff this exhausts some domain.
        private static bool Prune(int k)
        {
            var newSingletons = new Queue<int>();
            newSingletons.Enqueue(k);

            while (newSingletons.Count != 0)
            {
                k = newSingletons.Dequeue();

                //Console.WriteLine("Pruning from domain {0}.", k);

                var b = D[k];
                for (var j = 1; j <= N; j++)
                {
                    if (j == k) continue;
                    var dOrig = D[j];
                    var d = dOrig;
                    d = RemoveBitFromDomain(d, b);
                    d = RemoveBitFromDomain(d, b << (k + 1));
                    d = RemoveBitFromDomain(d, b >> (j + 1));
                    d = RemoveBitFromDomain(d, (b << (k + 1)) >> (j + 1));
                    if (DomainIsEmpty(d)) return false;
                    if (d != dOrig)
                    {
                        TrailDomainValue(j);
                        D[j] = d;
                        if (DomainIsSingleton(d)) newSingletons.Enqueue(j);
                    }
                }

                //WriteDomains();
            }
            return true;
        }

        // Search for a solution.  Return false iff one is not found.
        private static bool FindSolution() {
            var k = SmallestUndecidedDomainIndex();
            if (k == 0) return true;

            // Branch on k, trying each possible assignment.
            var dOrig = D[k];
            var d = dOrig;
            var checkPoint = TTop;
            while (!DomainIsEmpty(d))
            {
                var b = LeastBitInDomain(d);
                d = RemoveBitFromDomain(d, b);
                D[k] = b;

                //Console.WriteLine();
                //Console.WriteLine("Branching on domain {0}.", k);

                if (Prune(k) && FindSolution()) return true;
                UntrailTo(checkPoint);
            }
            D[k] = dOrig;
            return false;
        }

        // Print out a representation of the domains.
        private static void WriteDomains()
        {
            for (var k = 1; k <= N; k++)
            {
                Console.Write("D[{0,3}] = {{", k);
                for (var i = 1; i <= N + N; i++)
                {
                    Console.Write("{0, 3}", ( (1 << i) & D[k]) != 0 ? i.ToString() 
                                            : DomainIsSingleton(D[k]) && (1 << i) == (D[k] << (k + 1)) ? "x"
                                            : "");
                }
                Console.WriteLine(" }");
            }
        }

        // Set up the problem.
        private static void InitLangford(int n)
        {
            N = n;
            D = new int[N + 1];
            var bs = (1 << (N + N - 1)) - 1;
            for (var k = 1; k <= N; k++)
            {
                D[k] = bs & ~1;
                bs >>= 1;
            }
        }
    }
}