有限正整数集合中任何两个数的差均不相同，求该集合最大元素的最小值

问题：有限正整数集合中任何两个数的差均不相同，求该集合最大元素的最小值
该问题最初由 del_c_sharp(头大中......)提出，mathe()、ALNG(?)、Lawrence444(胖子)、gofor()等积极参与:
http://www.csdn.net/expert/topic/931/931488.xml?temp=.9010126
http://www.csdn.net/expert/topic/934/934268.xml?temp=.1472284
http://www.csdn.net/expert/topic/954/954026.xml?temp=.4488336

我写了一个C#程序用于解决该问题，使用穷举法。该程序参考了Lawrence444(胖子)的C程序。我的C#程序有以下特点：
1. 可以随时中断程序的运行，下次运行时接着从断点处开始计算。
2. 可以求解集合元素个数为 [2,36] 之间的问题。
3. 如果从 2、3、4 ... 连续求解，速度最快，程序会自动生成 best.txt 文件。
4. 或者手工编辑一个 best.txt 文件：1 2 4 7 12 18 26 35 45 56 73 86 107 128。

源程序如下：
// microblue (R) NList Program Version 1.00  (C)Sat 2002.08.31
using System;
using System.IO;

namespace Microblue.Other.NList
{
  class MainEntry
  {
    static void Main(string [] args)
    {
      try {
        new NList((args.Length > 0) ? Convert.ToInt32(args[0]) : 8);
      }
      catch (Exception err)
      {
        Console.WriteLine(err.Message);
      }
    }
  }

  // 有限正整数集合中任何两个数的差均不相同，求该集合最大元素的最小值
  class NList
  {
    const int Q_SIZE = 3000;
    
    public NList(int n)
    {
      DateTime begin = DateTime.Now;
      if (n < 2 || n > 36) throw new Exception("parameter must in [2, 36]");
      bool [] q = new bool [Q_SIZE];
      int [] p = new int [n], t = new int [n - 1];
      int i, k = 1, m = int.MaxValue, x, z = n * (n - 1) / 2 + 1;
      string s, fn = "n" + n + ".txt", fb = "best.txt";
      if (!File.Exists(fb))
      {
        StreamWriter sb = new StreamWriter(fb);
        sb.WriteLine("1");
        sb.Close();
      }
      StreamReader sr = new StreamReader(fb);
      if ((s = sr.ReadLine()) == null) throw new Exception("Error in read file: " + fb); 
      string [] ps = s.Split();
      for (i = 0; i < ps.Length && i < n - 1; i++) t[i] = Convert.ToInt32(ps[i]) - 1;
      for (x = ps.Length; i < n - 1; i++) t[i] = i * (i - 1) / 2;
      sr.Close();
      bool b = File.Exists(fn);
      if (b)
      {
        Console.WriteLine("Continue from FILE: [{0}]", fn);
        string s2 = null;
        sr = new StreamReader(fn);
        while ((s = sr.ReadLine()) != null) s2 = s;
        sr.Close();
        if (s2 == null) throw new Exception("FILE: Empty");
        if (s2.Substring(0, 3) == "End") throw new Exception("FILE: End");
        Console.WriteLine(s2);
        ps = s2.Split();
        if (ps.Length != n + 2) throw new Exception("FILE: Invalid field number");
        for (i = 2; i < ps.Length; i++)  p[n - (i - 1)] = Convert.ToInt32(ps[i]);
        FullCheck(ref q, p); // must, for make (q)
        m = p[k = n - 1];
        StepClear(q, p, k);
        StepClear(q, p, --k);
      }
      StreamWriter sw = new StreamWriter(fn, true);
      if (!b)
      {
        p[0] = p[1] = 1;
        s = "Begin: " + begin;
        Console.WriteLine(s);
        sw.WriteLine(s);
      }
      for (;;)
      {
        if (k <= 0) break;
        if (k == 1 && p[k] != 1) Console.Write("{0} ", p[k] + 1);
        if (++p[k] >= m - t[n - 1 - k]) StepClear(q, p, --k);
        else if (StepCheck(q, p, k))
        {
          if (k >= n - 1) // assert: k == n - 1
          {
            s = n + ": (" + z + ")";
            for (i = k; i >= 0; i--) s += " " + p[i];
            Console.WriteLine(s);
            sw.WriteLine(s);
            sw.Flush();
            FullCheck(ref q, p); // not must, only verify
            m = p[k];
            StepClear(q, p, k);
            StepClear(q, p, --k);
          }
          else
          {
            p[k + 1] = p[k];
            k++;
          }
        }
      }
      if (n == x + 1)
      {
        StreamWriter sb = new StreamWriter(fb);
        foreach (int j in t) sb.Write(j + 1 + " ");
        sb.WriteLine(p[x]);
        sb.Close();
      }
      DateTime end = DateTime.Now;
      s = "End: " + end + " ";
      s += b ? "Continue from FILE" : (end - begin).ToString();
      Console.WriteLine("\n" + s);
      sw.WriteLine(s);
      sw.Close();
    }
    
    bool StepCheck(bool [] q, int [] p, int n)
    {
      for (int pn = p[n], j = 0; j < n; j++) if (q[pn - p[j]]) return false;
      for (int pn = p[n], j = 0; j < n; j++) q[pn - p[j]] = true;
      return true;
    }

    void StepClear(bool [] q, int [] p, int n)
    {
      for (int pn = p[n], j = 0; j < n; j++) q[pn - p[j]] = false;
    }

    void FullCheck(ref bool [] q, int [] p)
    {
      q = new bool [Q_SIZE];
      for (int i = 1; i < p.Length; i++)
        for (int pi = p[i], j = 0; j < i; j++)
        {
          int v = pi - p[j];
          if (q[v]) throw new Exception("Verify fail");
          q[v] = true;
        }
    }
  }
}

13 个解决方案

#1

考虑到很多人没有C#环境，我把上面那个程序有C/C++改写了一下：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#include <mem.h>

const int Q_SIZE = 3000;
const int S_SIZE = 1024;
const int N_SIZE = 36;

void ErrorExit(const char *s1, const char *s2)
{
  fprintf(stderr, "%s%s\n", s1, s2);
  exit(1);
}

int StepCheck(int * q, int * p, int n)
{
  for (int pn = p[n], j = 0; j < n; j++) if (q[pn - p[j]]) return 0;
  for (pn = p[n], j = 0; j < n; j++) q[pn - p[j]] = 1;
  return 1;
}

void StepClear(int * q, int * p, int n)
{
  for (int pn = p[n], j = 0; j < n; j++) q[pn - p[j]] = 0;
}

void FullCheck(int * q, int * p, int n)
{
  memset(q, 0, Q_SIZE * sizeof(int));
  for (int i = 1; i < n; i++)
    for (int pi = p[i], j = 0; j < i; j++)
    {
      int v = pi - p[j];
      if (q[v]) ErrorExit("Verify fail", "");
      q[v] = 1;
    }
}

void NList(int n)
{
  time_t begin = time(NULL);
  int q[Q_SIZE] = {0};
  int p[N_SIZE], t[N_SIZE - 1];
  int i, k = 1, m = INT_MAX, x, z = n * (n - 1) / 2 + 1;
  char s[S_SIZE], fn[20], *fb = "best.txt";
  sprintf(fn, "n%d.txt", n);
  FILE * sr;
  if ((sr = fopen(fb, "rt")) == NULL) {
   sr = fopen(fb, "wt");
   fprintf(sr, "1\n");
   fclose(sr);
   sr = fopen(fb, "rt");
  }
  if (fgets(s, S_SIZE, sr) == NULL) ErrorExit("Error in read file: ", fb);
  fclose(sr);
  char *ps = s;
  while (isspace(*ps)) ps++;
  for (i = 0; isdigit(*ps); i++) {
    if (i < n - 1) t[i] = atoi(ps) - 1;
    while (isdigit(*ps)) ps++;
    while (isspace(*ps)) ps++;
  }
  x = i;
  for (; i < n - 1; i++) t[i] = i * (i - 1) / 2;
  int b = 0;
  if ((sr = fopen(fn, "rt")) != NULL) {
   fclose(sr);
   b = 1;
  }
  if (b) {
    printf("Continue from FILE: [%s]\n", fn);
    char s2[S_SIZE] = {0};
    sr = fopen(fn, "rt");
    while ((fgets(s, S_SIZE, sr)) != NULL) sprintf(s2, "%s", s);
    fclose(sr);
    if (s2[0] == 0) ErrorExit("FILE Empty: ", fn);
    if (s2[0] == 'E' && s2[1] == 'n' && s2[2] == 'd') ErrorExit("FILE End: ", fn);
    printf("%s\n", s2);
    ps = s2;
    while (isspace(*ps)) ps++;
    while (!isspace(*ps) && *ps != '\0') ps++;
    while (isspace(*ps)) ps++;
    while (!isspace(*ps) && *ps != '\0') ps++;
    while (isspace(*ps)) ps++;
    for (i = 2; isdigit(*ps) && i < n + 2; i++) {
      p[n - (i - 1)] = atoi(ps);
      while (isdigit(*ps)) ps++;
      while (isspace(*ps)) ps++;
    }
    if (i != n + 2) ErrorExit("Invalid field number in FILE: ", fn);
    FullCheck(q, p, n);
    m = p[k = n - 1];
    StepClear(q, p, k);
    StepClear(q, p, --k);
  }
  FILE *sw;
  if ((sw = fopen(fn, "at")) == NULL) ErrorExit("Can not write FILE: ", fn);
  if (!b) {
    p[0] = p[1] = 1;
    sprintf(s, "Begin: %s", ctime(&begin));
    printf("%s\n", s);
    fprintf(sw, "%s\n", s);
  }
  for (;;) {
    if (k <= 0) break;
    if (k == 1 && p[k] != 1) printf("%d ", p[k] + 1);
    if (++p[k] >= m - t[n - 1 - k]) StepClear(q, p, --k);
    else if (StepCheck(q, p, k)) {
      if (k >= n - 1) { // assert: k == n - 1
        sprintf(s, "%d: (%d)", n, z);
        for (i = k; i >= 0; i--) {
          char s1[20];
          sprintf(s1, " %d", p[i]);
          strcat(s, s1);
        }
        printf("%s\n", s);
        fprintf(sw, "%s\n", s);
        fflush(sw);
        // FullCheck(q, p, n); // not must, only verify
        m = p[k];
        StepClear(q, p, k);
        StepClear(q, p, --k);
      }
      else {
        p[k + 1] = p[k];
        k++;
      }
    }
  }
  if (n == x + 1) {
    FILE *sb;
    if ((sb = fopen(fb, "wt")) == NULL) ErrorExit("Can not write FILE: ", fb);
    for (i = 0; i < n - 1; i++) fprintf(sb, "%d ", t[i] + 1);
    fprintf(sb, "%d\n", p[x]);
    fclose(sb);
  }
  time_t end = time(NULL);
  sprintf(s, "End: %s", ctime(&end));
  if (!b) {
    char s1[20];
    sprintf(s1, "End: (%ld seconds used)", long(end - begin));
    strcat(s, s1);
  }
  printf("\n%s\n", s);
  fprintf(sw, "%s\n", s);
  fclose(sw);
}

int main(int argc, char *argv[])
{
  int n = 8;
  if (argc > 1) n = atoi(argv[1]);
  if (n >= 2 && n <= 36) NList(n);
  return 0;
}

因为C#要做数组边界检查，而C/C++不做检查，理论上这个版本运行速度应该更快。但在我的机器上正好相反，不知问题出在哪里。

#2

开这么多贴会分散大家的注意力。不如集中把几个贴炒热。这个贴吸引了很多高人[可惜startfish一直没有参与]，我长了不少眼界，也深感自己数学太差。准备学习一点基础的数论，还有运筹学[跟这个问题无关]。

#3

我认为你举的这个例子好象不正确，如果说任何两个数的差均不相同，则你的这个例子：1 2 4 7 12 18 26 35 45 56 73 86 107 128中，4 - 1 = 3,7 - 4 = 3,这就不对了，是我理解错你的题意了还是你的举例不正确？
  我有一个算法，得到的集合中，任意两个数的差都不相同：2^n
 即：1,2,4,8,16,32...
  不知我说的对不对，仅供参考。

#4

补充：这样做法会漏掉一些数所以不对，算我没说好了。

#5

gz

#6

很早就看到都热火朝天的讨论这道题.
我就是看不懂.我只会用穷举.
我想知道这道题的背景,比如应用于什么地方了,如果就题论题,比这道题难的多的题多的是.

#7

To: qiuyang_wang(小数点):
best.txt 文件: 1 2 4 7 12 18 26 35 45 56 73 86 107 128
是在该程序中用来减少计算量的数组，指的是元素个数为 1,2,3,...的所求的集合的最大元素的最小值，而不是所求的集合本身，你看看源程序就会明白，如下所列：
 1: (1) 1
 2: (2) 2 1
 3: (4) 4 2 1
 4: (7) 7 5 2 1
 5: (11) 12 10 5 2 1
 6: (16) 18 13 11 5 2 1
 7: (22) 26 24 19 11 5 2 1
 8: (29) 35 33 23 16 10 5 2 1
 9: (37) 45 42 36 28 26 13 6 2 1
10: (46) 56 54 42 35 27 24 11 7 2 1
11: (56) 73 71 65 55 48 34 29 14 5 2 1
12: (67) 86 77 76 69 56 44 41 30 25 7 3 1
13: (79) 107 100 99 90 86 71 60 44 38 26 6 3 1
14: (92) 128 123 100 90 87 79 78 60 53 36 21 7 5 1
以上是我用该C#程序计算出来的头14个最优解，第15个解正在计算过程中。

#8

由序列的对偶性，搜索时可以假定第1个差值小于第2个差值，仅此假定就可节省40%多的时间，如检查n=13是否存在最大值为100的解时，耗时由44464ms减少到26168ms。

#9

me认为下面两位大虾的话有道理：
 qiuyang_wang(小数点):  我认为你举的这个例子好象不正确，如果说任何两个数的差均不相同，则你的这个例子：1 2 4 7 12 18 26 35 45 56 73 86 107 128中，4 - 1 = 3,7 - 4 = 3,这就不对了，是我理解错你的题意了还是你的举例不正确？
  我有一个算法，得到的集合中，任意两个数的差都不相同：2^n
 即：1,2,4,8,16,32...
  不知我说的对不对，仅供参考。

alidiedie(阿里) ： 我想知道这道题的背景,比如应用于什么地方了,如果就题论题,比这道题难的多的题多的是.

#10

To: gofor():
> 由序列的对偶性，搜索时可以假定第1个差值小于第2个差值，仅此假定就可节省40%多的时间，...
请问一下，上面“第1个差值”和“第2个差值”分别是指什么？以
14: (92) 128 123 100 90 87 79 78 60 53 36 21 7 5 1 
为例，“第1个差值”是不是指: 5 - 1 = 4，“第2个差值”是不是指：7 - 5 = 2。如果是这样，“第1个差值”并不小于“第2个差值”。
如果“第1个差值”是指：5 - 1 = 4，“第2个差值”是指：128 - 123 = 5 的话，这倒是可以由序列的对偶性保证的，但是好象对提高算法的速度所起的作用不大，无法达到节省 40% 多的时间的效果。
请 gofor() 给予解答，谢谢！

#11

第1个差值从哪边算起无所谓，不妨假定从大端算起。
我的本意是：如果一个最优解序列不满足条件“第1个差值小于第2个差值”，则其对偶序列一定满足该条件，即一定存在一个满足该条件的最优解序列。这样，在用穷举法搜索最优解时，就只要搜索满足“第1个差值小于第2个差值”的解序列。节省40%是实验验证的，其原因也不难理解，因为省去了对“第1个差值大于第2个差值”的所有情况的搜索判断，这几乎是一半。
但我现在发现我的一个逻辑错误，“如果一个最优解序列不满足条件‘第1个差值小于第2个差值’，则其对偶序列一定满足该条件”并不成立。不过，从已知n<=14的最优解的情况来看，都存在一个满足该条件的最优解序列。

#12

1 7 8 16 29 41 52 76 90 93 95 122 132 148 152
以上很可能是n=15时的最优解。之所以说“很可能”，是因为我用了几个未被证明的假设：
1、第1个差值小于第2个差值
2、使用1,2,4,9,13,22,33,42,54,70,77,100,123,138而不是1,2,4,7,12,18,26,35,45,56,73,86,107,128做为各位置的最小值。
3、仅搜索了142~152的区间。
历时约12小时。

#13

用无最大差值限制的动态边界搜索法，搜索n=16，得到一个更好的序列，我原以为179是最好的结果，这说明最大差值限制的不可靠性。
1 10 15 28 44 61 63 102 110 122 146 152 167 174 177 178
其差值序列为9 5 13 16 17 2 39 8 12 24 6 15 7 3 1

现正在继续搜索。