“排序”通常使用二进制比较运算符(“小于或等于”)定义。您要寻找的是列表的“最佳”排列,其中“最佳”定义为在整个列表上定义的标准(虽然“特定函数”在相邻元素上定义,但整个列表上的总和使其成为全局属性)。

如果我理解正确的话,“旅行推销员”就是你问题的一个例子,所以你的问题是NP完全的;-)

因为使用的函数没有限制

a^b也可以是在任意数量的连续元素上运行的任何函数。

如果使用一个常量函数(比如alwasys返回1),那么所有排序的和都是相同的,但在查看所有排序之前,您不一定知道这一点。

所以我看不到比计算所有排列的函数和和更快的了。

编辑:另外,由于它可能是一个作用于所有元素的函数,因此可以有一个函数,该函数对所有置换返回0,但对其中一个置换返回1。

所以对于一般情况,你肯定需要计算所有置换的函数。

Optimization Probelm ,而不是排序问题。

我敢打赌,只要有一点点(或者很多)的工作,有人就会证明这在功能上等同于一个著名的NP完全问题。但是,对于某些特定函数(例如示例中的^b),问题可能更容易解决。

如果不是,那就是一个动态规划问题。要了解它,您应该以您的示例为基础,将您的问题转化为以下问题。你在一开始。您可以选择{1,2,3,4}中的任意一个。从那里你可以选择去{1,2,3,4}。这样做4次,你就得到了列表{1,2,3,4}中长度4的所有排列。

现在您需要一个成本函数,其定义如下:

f(prev, next) = prev ^ next
              = 0 if the solution is not valid for your original problem 
              = 0 if prev is the start

总成本表示为:

cost(i|a|X) = min(i in {1,2,3,4}, f(i, a) + cost(X))

注意 i|a|X 表示一个列表,从元素a开始,然后是i,列表的其余部分是X。

cost 函数您应该识别动态编程。

从那里你可以导出一个算法。查看维基百科,了解更多信息 introduction to dynamic programming .

(define (cost lst f)
  (if (null? lst)
      0
      (let ((h (car lst))
            (t (cdr lst)))
        (if (null? t)
            0
            (+ (f h (car t))
               (cost t f))))))

(define (solve lst f)
  (let loop ((s '()))
    (if (= (length s) (length lst))
        s
        (loop
         (let choose ((candidate lst)
                      (optimal #f)
                      (optimal-cost #f))
           (if (null? candidate)
               optimal
               (let ((c (car candidate)))
                 (if (memq c s)
                     (choose (cdr candidate) optimal optimal-cost)
                     (if (not optimal) 
                         (choose (cdr candidate) (cons c s) (cost (cons c s) f))
                         (if (<= (cost (cons c s) f)
                                 (cost optimal f))
                             (choose (cdr candidate) (cons c s) (cost (cons c s) f))
                             (choose (cdr candidate) optimal optimal-cost)))))))))))

(solve '(1 2 3 4) expt) 产生另一个最小解'(3 2 1 4)。

强力攻击

    public static int Calculate(Func<int, int, int> f, IList<int> l)
    {
        int sum = 0;
        for (int i = 0; i < l.Count-1; i++)
        {
            sum += f(l[i], l[i + 1]);
        }
        return sum;
    }

    public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> list, int count)
    {
        if (count == 0)
        {
            yield return new T[0];
        }
        else
        {
            int startingElementIndex = 0;
            foreach (T startingElement in list)
            {
                IEnumerable<T> remainingItems = AllExcept(list, startingElementIndex);

                foreach (IEnumerable<T> permutationOfRemainder in Permute(remainingItems, count - 1))
                {
                    yield return Concat<T>(
                        new T[] { startingElement },
                        permutationOfRemainder);
                }
                startingElementIndex += 1;
            }
        }
    }

    // Enumerates over contents of both lists.
    public static IEnumerable<T> Concat<T>(IEnumerable<T> a, IEnumerable<T> b)
    {
        foreach (T item in a) { yield return item; }
        foreach (T item in b) { yield return item; }
    }

    // Enumerates over all items in the input, skipping over the item
    // with the specified offset.
    public static IEnumerable<T> AllExcept<T>(IEnumerable<T> input, int indexToSkip)
    {
        int index = 0;
        foreach (T item in input)
        {
            if (index != indexToSkip) yield return item;
            index += 1;
        }
    }

    public static void Main(string[] args)
    {
        List<int> result = null;
        int min = Int32.MaxValue;
        foreach (var p in Permute<int>(new List<int>() { 1, 2, 3, 4 }, 4))
        {
            int sum = Calculate((a, b) => (int)Math.Pow(a, b), new List<int>(p));
            if (sum < min)
            {
                min = sum;
                result = new List<int>(p);
            }
        }
        // print list
        foreach (var item in result)
        {
            Console.Write(item);
        }
    }

我从你那里偷了排列码 Ian Griffiths blog

这绝对不是一个排序列表。如果您有一个排序列表[x~0~…x~n~],则该列表 [x~0~…x~i-1~,x~i+1~…x~n~](即x~i~删除)也将根据定义进行排序。在您的示例中,从子序列100,0100中删除0很可能会取消列表的排序。

这就是我目前所拥有的。我创建了一个Calc类,我可以将我的每个组合传递给它,然后它计算总数,并有一个ToString()方法,因此您不必担心迭代以输出总和字符串和值。您可以获取构造函数中传入的总计和列表。然后,您可以将每个组合集添加到列表中,您可以在

class Calc
{
    private int[] items;
    private double total;
    public double Total 
    { 
        get
        { 
            return total; 
        } 
    }
    public int[] Items
    {
        get { return items;  }
        set { total = Calculate(value); }
    }
    public static double Calculate(int[] n)
    {
        double t = 0;
        for (int i = 0; i < n.Length - 1; i++)
        {
            int a = n[i]; int b = n[i + 1];
            t += a^b;
        }
        return t;
    }
    public Calc(int[] n)
    {
        this.items = n;
        this.total = Calculate(n);
    }
    public override string ToString()
    {
        var s = String.Empty;
        for (int i = 0; i < items.Length - 1; i++)
        {
            int a = items[i]; int b = items[i + 1];
            s += String.Format("{0}^{1}", a, b);
            s += i < items.Length - 2 ? "+" : "=";
        }
        s += total;
        return s;
    }
}

然后我们在计算中使用类,并根据每个排列的总数快速排序:

class Program
{
    static void Main(string[] args)
    {
        var Calculations = new List<Calc>();

        ////Add a new item to totals for every combination of...working on this
        Calculations.Add(new Calc(new int[] { 1, 2, 3, 4 }));
        //...

        //Grab the item with the lowest total... if we wanted the highest, we'd
        //just change .First() to .Last()
        var item = Calculations.OrderBy(i=>i.Total).First();
        Console.WriteLine(item);
        //Or if we wanted all of them:
        //Calculations.OrderBy(i=>i.Total).ForEach(Console.WriteLine);
    }
}

但是,一旦给定了一个函数,您可以(可能)为该函数设计一种排序方法,例如,对于上面的a^b,将列表排序为Max、min、next Max、next min。然后颠倒顺序。

根据给定功能的复杂性,提供优化的排序例程将越来越困难。

谢谢

这个问题的解决方案将在很大程度上取决于您希望用于排序的方法。然而,乍一看,您可能需要迭代所有可能的订单以找到最小订单。如果当前总和大于以前的总和,则可能导致短路。

1. 对列表排序
2. 从排序列表中创建对,抓取第一个数字和最后一个数字,然后抓取第二个和倒数第二个数字,等等(即1,2,3,4变为1,4和2,3)

我猜不会那么简单。。。但这对你的例子来说是有效的,这不是真正重要的吗?