在组合数学中，Langford pairing也称为Langford序列，是2n编号1, 1, 2, 2, ..., n, n的序列的置换，其中两个1彼此分开一个单位，两个2彼此分开两个单位，更通常的是每个的两个副本数字k相距k个单位。
例如:n = 3的Langford配对由序列2,3,1,2,1,3.给出
haskell或C解决此问题的好方法是什么-------------------------- EDIT ----------------------
我们如何定义数学规则以将@Rafe的代码放入haskell
最佳答案
您想要找到对变量{p1，p2，...，pn}的赋值(其中pi是首次出现的“i”的位置)，并且每个pi都具有以下约束:
1 ..((1 + n-i)中的
您在这里需要一个明智的搜索策略。一个好的选择是在每个选择点上选择具有最小剩余可能值的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;
}
}
}
}
关于c - Langford序列实现Haskell或C，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5809712/