Это то, что у меня есть до сих пор. Я создал класс Calc, в который я могу передать каждую из моих комбинаций, затем он вычисляет сумму и имеет метод ToString (), поэтому вам не нужно беспокоиться об итерации для вывода строки суммы и значения. Вы можете получить общее количество и список, переданный в конструктор. Затем вы можете просто добавить каждый из своих наборов комбинаций в список, который вы можете отсортировать по LINQ в inst.Total ... как я продемонстрировал. Все еще работаю над средствами для создания каждой комбинации ...

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);
    }
}

Хм, это интересная проблема. Использование существующих конструкций сортировки (IComparable) не сработает, потому что вам нужно больше информации, чем доступно для метода compareTo.

Решение этой проблемы будет во многом зависеть от того, какой метод вы хотите использовать для сортировки. Однако на первый взгляд может показаться, что вам, вероятно, придется перебирать все возможные заказы, чтобы найти минимальный заказ. Вы можете потенциально замкнуть его, если текущая сумма больше, чем предыдущая общая сумма.

Я должен попробовать и посмотреть, что я могу придумать.

Поскольку нет ограничений на используемую функцию

also a^b could be any function operating over any number of consecutive elements.

если используется постоянная функция (скажем, та, которая всегда возвращает 1), сумма будет одинаковой для всех порядков, но вы не обязательно узнаете это, пока не посмотрите на все порядки.

Так что я не вижу ничего быстрее, чем вычисление функции и суммы для всех перестановок.

(Вы можете запоминать результаты для каждого кортежа, чтобы ускорить оценку, но я думаю, вам все равно нужно просмотреть их все)

Обновлено: Кроме того, поскольку это может быть функция, действующая на все элементы, у вас может быть функция, которая возвращала бы 0 для всех перестановок, кроме одной, для которой она возвращает 1.

Итак, в общем случае вам определенно нужно будет оценить функцию для всех перестановок.

Похоже, это Проблема оптимизации, а не проблема сортировки.

Бьюсь об заклад, немного (а может быть, много) работы кто-то может показать, что это функционально эквивалентно одной из известных проблем NP Complete. Однако для некоторых конкретных функций (например, a ^ b в вашем примере) проблема может быть проще.

Это определенно не отсортированный список. Если у вас есть отсортированный список [x ~ 0 ~ ... x ~ n ~], список [x ~ 0 ~ ..x ~ i-1 ~, x ~ i + 1 ~ ..x ~ n ~] (т.е. x ~ i ~ удалено) по определению также будет отсортировано. В вашем примере удаление 0 из подпоследовательности 100,0,100, скорее всего, приведет к отмене сортировки списка.

непроверенные и недоказанные:

1. Сортировать список
2. Создайте пары из отсортированного списка, захватывая первое число и последнее, затем второе и второе до последнего и т. д. (Т.е. 1,2,3,4 становятся 1,4 и 2,3)
3. Для каждой пары сохраните значение ^ b. Обратный отсортировать этот список
4. Замените значения a ^ b в новом списке на значения a и b.

Я предполагаю, что это не может быть так просто ... но это работает для вашего примера, и разве это не главное?

«Сортировка» обычно определяется с помощью оператора двоичного сравнения («меньше или равно»). То, что вы ищете, - это «лучшая» перестановка списка, где «лучший» определяется как критерий, который определяется для всего списка (в то время как «определенная функция» определяется для соседних элементов, сумма по всему списку делает его глобальным свойством).

Если я правильно понимаю, "коммивояжер" - это пример вашей проблемы, так что ваша проблема в любом случае является NP-полной ;-)

Это полная проблема NP, потому что алгоритм неизвестен (NB для данной функции a ^ b это не NP Complete, это можно сделать за один проход после сортировки, см. Пример ниже для решения)

Невозможно заранее написать «алгоритм сортировки» без вычисления результатов данной функции для всех возможных перестановок списка.

Однако, получив функцию, вы можете (возможно) разработать для нее метод сортировки, например. для a ^ b выше, упорядочьте список таким образом (без применения функции к каким-либо элементам) «Макс, мин, следующий максимум, следующий минимум. . . »И поменяйте этот порядок в обратном порядке.

В зависимости от сложности данной функции будет все труднее предоставлять оптимизированные процедуры сортировки.

Спасибо,

Это домашнее задание?

В противном случае это проблема динамического программирования. Чтобы увидеть это, вы должны преобразовать вашу проблему в следующую, взяв за основу ваш пример. Вы в самом начале. Вы можете выбрать один из {1,2,3,4}. Оттуда вы можете перейти к {1,2,3,4}. Сделайте это 4 раза, и у вас будет все расположение длины 4 из списка {1,2,3,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, вы должны распознать динамическое программирование.

Оттуда вы можете вывести алгоритм. Посмотрите википедию, чтобы найти введение в динамическое программирование.

Моя реализация схемы, которую вы можете протестировать с помощью схемы PLT:

(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);
        }
    }

Я украл код перестановки из Блог Иэна Гриффитса.