Алгоритм минимального изменения, который максимизирует 'свопинг'

Это довольно просто. Чтобы максимизировать замену, просто думайте о символах как о числах и увеличивайте строку на одну, пока не достигнете верхнего предела. Затем проверьте, не используется ли один и тот же символ дважды в строке. Я думаю, что это сработает:

char c[] = {'a', 'b', 'c', 'd', 'e'};
const int n = 5;
const int k = 3;
char s[k];

void print()
{
    for( int i = 0; i < k; ++i )
        putchar(c[s[i]]);
    putchar('\n');
}

bool increment( int m )
{
    // reached the limit?
    if( ++s[m] == n && m == 0 )
        return false;

    next:   
    for( int i = 0; i < m; ++i )
    {
        if( s[m] == n )
        {
            // carry
            s[m] = 0;
            if( !increment( m-1 ))
                return false;
            goto next;
        }
        else if( s[i] == s[m] )
        {
            // the character is already used
            ++s[m];
            goto next;
        }   
    }
    return true;
}

int main(int, char**)
{   
    // initialise
    for( int i = 0; i < k; ++i )
        s[i] = i;

    // enumerate all combinations
    do
        print();
    while(increment(k-1));
}

Ким, ваше описание проблемы звучит очень похоже на попытку (домашнее задание) описать простейшее решение для перечисления всех k-комбинаций набора из n элементов - не выдавая фактического решения слишком легко. В любом случае, смотрите ниже мою попытку. Я использовал Java, но важные части не отличаются от C.

public class Homework
{
  /**
   * Prints all k-combinations of a set of n elements. Answer to this 
   * question: http://stackoverflow.com/questions/2698551
   */
  public static void main(String[] args)
  {
    Combinations combinations = new Combinations(7, 3);
    System.out.printf(
        "Printing all %d %d-combinations of a set with %d elements:\n", 
        combinations.size(), combinations.k, combinations.n);
    for (int[] c : combinations)
      System.out.println(Arrays.toString(c));
  }

  /**
   * Provides an iterator for all k-combinations of a set of n elements. 
   */
  static class Combinations implements Iterable<int[]>  
  {
    public final int n, k;

    public Combinations(int n, int k)
    {
      if (n < 1 || n < k)
        throw new IllegalArgumentException();
      this.n = n;
      this.k = k;
    }

    @Override
    public Iterator<int[]> iterator()
    {
      return new Iterator<int[]>()
      {
        private int[] c;

        @Override
        public void remove() { throw new UnsupportedOperationException(); }

        @Override
        public int[] next()
        {
          if (c == null)
          {
            c = new int[k];
            for (int i = 0; i < k; i++)
              c[i] = i;
          }
          else
          {
            int i = c.length - 1;
            while (i >= 0 && c[i] == n - k + i)
              i--;

            if (i < 0)
              throw new NoSuchElementException();

            c[i]++;
            for (int j = i + 1; j < c.length; j++)
              c[j] = c[i] + j - i;
          }
          return c.clone(); // remove defensive copy if performance is more important
        }

        @Override
        public boolean hasNext() { return c == null || c[0] < n - k; }
      };
    }

    /**
     * Returns number of combinations: n! / (k! * (n - k)!).
     */
    public BigInteger size()
    {
      BigInteger s = BigInteger.valueOf(n);
      for (int i = n - 1; i > n - k; i--)
        s = s.multiply(BigInteger.valueOf(i));
      for (int i = k; i > 1; i--)
        s = s.divide(BigInteger.valueOf(i));
      return s;
    }
  }
}

Вот вывод для вашего примера:

Printing all 35 3-combinations of a set with 7 elements:
[0, 1, 2] [0, 1, 3] [0, 1, 4] [0, 1, 5] [0, 1, 6] [0, 2, 3] [0, 2, 4] [0, 2, 5] [0, 2, 6] [0, 3, 4] 
[0, 3, 5] [0, 3, 6] [0, 4, 5] [0, 4, 6] [0, 5, 6] [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 2, 6] [1, 3, 4] 
[1, 3, 5] [1, 3, 6] [1, 4, 5] [1, 4, 6] [1, 5, 6] [2, 3, 4] [2, 3, 5] [2, 3, 6] [2, 4, 5] [2, 4, 6] 
[2, 5, 6] [3, 4, 5] [3, 4, 6] [3, 5, 6] [4, 5, 6] 

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

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

Я начал с представления набора комбинаций как вершин в графе с ребрами, соответствующими «смежности» (разница только в одном элементе) комбинаций. Итак:

• «n выбрать k» вершин
• каждая вершина имеет степень k (nk)
• количество ребер = «n выбрать k» * k (nk) / 2 = «n выбрать 2» * «n -2 choose k-1 "

Эти графы очень симметричны. График такой же для любого заданного {n, k}, как и для {n, n-k}. Если k = 1 или k = n-1, это полный граф на n вершинах (каждая комбинация отличается от всех остальных только одним символом). Однако я не вижу здесь очевидного алгоритма.

Edit: Моя следующая мысль заключалась в том, чтобы представить график с несколько иной интерпретацией. Вы можете думать о каждой {n, k} -комбинации как о последовательности из n битов, где есть k единиц. Положение единиц соответствует тому, какой из n символов присутствует в комбинации. Итак, для n = 7 k = 3, abc равно 1110000, adg равно 1001001, efg равно 0000111. С его помощью вы также можете представить себе точки, лежащие в углах n-мерного гиперкуба. Итак, для данной подпоследовательности ребра соответствуют критериям «минимальной замены», если они копланарны: я думаю о них как о «плоскостях, разрезающих» гиперкуб.

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

Другой способ подумать о вашей проблеме - это минимизировать количество раз в последовательности, когда вы делаете изменение, какой символ в комбинации изменяется.

Чтобы получить хороший ответ, вычисление список комбинаций всех сразу приемлем, или вам нужно вычислять их по одной за раз? Другими словами, вам нужна функция:

Combination nextCombo();

или

vector<Combination> allCombinations();

будет приемлемым?

Если вычисление комбинаций в пакетном режиме допустимо, возможно, что итеративно-углубляющий поиск A * (или просто A * поиск, но я подозреваю, что у него закончилась память) будет работать. При допустимой эвристике A * гарантированно дает оптимум. У меня мало времени, поэтому я решил опубликовать этот частичный ответ и отредактировать сообщение, если у меня будет время написать код.

A * - алгоритм поиска по графу. В этом случае узлы представляют собой списки комбинаций, которые использовались до сих пор (в списке не допускаются дубликаты). Мой план состоял в том, чтобы использовать представление узлов в виде битовой строки. n = 30 поместится в 32-битное целое число. Мы можем произвольно переставить любое решение так, чтобы первая комбинация начиналась с нулей и заканчивалась единицами, то есть 000 ... 1111.Узел с более коротким списком соединяется с более длинным, если два списка одинаковы до последнего элемента, а последний элемент отличается только тем, что один нулевой бит перевернут в 1, а один бит 1 - на 0.. расстояние между ними равно 0, если произошел «своп», и 1, если был своп.

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

Чтобы проиллюстрировать эту эвристику, рассмотрим последовательность abc abd abe * abf * abg afg сверху. (буквы были бы числами в моем обращении, но это незначительное различие). В этой последовательности (которая будет одним узлом в графе поиска) будут отмечены следующие места:

 1   2   3
*a      
 b  *b   
 c   c  *c
 d   d  *d
 e   e  *e
    *f  *f
        *g

Таким образом, эвристика предсказывает, что требуется по крайней мере один обмен (поскольку в позиции 3 нет неотмеченных элементов и текущая позиция 2).

Если у меня будет время, я отредактирую это, чтобы указать код публикации и производительность алгоритма.

Re: результат полноты NP (в комментарии к ответу Зака ​​Томпсона). Граф, на котором мы ищем гамильтонов путь минимальной стоимости, имеет особую структуру. Например, обычно NP-полная проблема гамильтонова пути может быть решена за время O (n) с помощью алгоритма «перечислить все комбинации», где n - количество узлов в графе.Эта структура делает возможным, что, хотя на обычном графе покрытие вершин является жестким, на вашем графике оно может быть полиномиальным (даже линейным или квадратичным). Конечно, поскольку в графе много узлов, например, n = 30, k = 8, возможно, впереди еще много вычислений.