Расположите пары чисел так, чтобы члены смежных пар были равны

Ответ 1

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

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Это, вероятно, не самое оптимизированное решение (сложность O (N!)), но его очень просто реализовать, если вам разрешено использовать рекурсию

(это не код objective-c, это алгоритм, переведите его сами, извините, я не знаю objective-c)

list function sortTupleList(list a, list b) //b is the current list
  list biggest = newlist()
  int target = b.last()[1]
  for(tuple k in a)
    if (k[0] == target)
      list n = sortTupleList(a.remove(k), b.add(k))
      if(n.size > biggest.size())
        biggest = n
      end if
    end if
  end for
  if (biggest == emptylist)
    return b
  else
    return biggest
end function


list function caller(list a)
  list b = newlist()
  b.add(12-8)
  a.remove(12-8)
  return sortTupleList(a,b)
end function

Эта функция проверяет каждый шаблон, начиная с 12-8 и сравнивая их размер

Ответ 2

В зависимости от размера вашей проблемы (n количество фрагментов) вы можете выбрать один из следующих способов:

1- Bruteforce: вы можете проверить все возможные конфигурации плиток с использованием обратного отсчета, что приведет к алгоритму сложности O(n!).

2- Битмакс Динамическое программирование: вы можете использовать динамическое программирование с помощью битовой маски, чтобы уменьшить пространство поиска. Такой подход приведет к алгоритму O(2^n * n).

Ответ 3

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

Сначала постройте граф таким образом, чтобы каждый отредактированный элемент соответствовал краю графа. Например, если ваш ввод указан как: 1-2, 2-3; вы строите граф с узлами: 1, 2, 3; и ребра (1, 2), (2, 3).

После этого вы увидите, что ваша проблема идентична поиску самого длинного пути, то есть самого длинного пути, который не содержит какого-либо ребра более одного. К сожалению, эта проблема известна как NP-hard, как обсуждалось в этом question. Таким образом, мы не можем надеяться найти полиномиальный алгоритм для решения этой проблемы.

Однако эта проблема на самом деле очень похожа на проблему Eularian Path. Однако на пути Eularian вы пересекаете все ребра. И это имеет очень простое решение:

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

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

Затем вы просто подсчитываете степень каждого node и проверяете, имеет ли этот граф эйлеровский путь по предыдущему определению. Если да, то тебе повезло. Потому что вы не можете иметь цепочку дольше, чем этот путь.

И вы можете легко вычислить эту цепочку Fleury Algorithm.

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

Подтверждающая лемма сообщает нам:

Каждый неориентированный граф имеет четное число вершин с нечетной степенью.

Если не существует эйлерова пути, то мы знаем, что у нас есть 2k-узлы с нечетными степенями, где k > 1. Поэтому нам нужно удалить минимальное число ребер, так что мы имеем k = 1. Однако вам нужно чтобы учесть, что при удалении некоторых краев оставшиеся ребра могут не подключаться.

Итак, лучшая эвристика, которая приходит мне на ум, заключается в том, чтобы найти ребра, чтобы обе его вершины имели нечетные степени, а удаление их не разрывает связную компоненту. Если мы найдем такие k - 1 вершины, то при их удалении мы будем иметь связную компоненту и у нас будет только 2 вершины с нечетными градусами. Поэтому мы можем найти самую длинную цепь легко, снова найдя эйлеровский путь, используя алгоритм Флери.

Ответ 4

Подумайте о числах в виде вершин и пар в качестве ребер графа (поэтому могут быть несколько многогранников). Теперь ваша проблема сводится к поиску самого длинного пути на графике, где могут повторяться вершины (но не ребра).

Ответ 5

Сохраняясь с идеей об ошибке, мы можем определить состояние для графа как число ребер, число вершин с нечетными степенями, хеш вершин и их связей, а также множество ребер с вершиной нечетной степени. Мы можем определить приоритеты состояний по числу ребер, вычитаемых на min(2, number of vertices with odd degree), или на ноль, если число вершин нечетной степени равно 2.

Ниже приведена попытка реализации JavaScript, использующая кучу для очереди приоритетов. Каждое ребро с вершиной нечетной степени удаляется по очереди, граф анализируется и разбивается на любые отдельные компоненты, когда это применимо, и каждый компонент помещается в очередь приоритетов. Цикл выходит рано, надеемся, гарантируя, что первый граф, возвращенный с эйлеровым путем, также имеет самый длинный из таких достижимых результатов.

var Heap = function (f){
  this.heap = [];
  this.isPriority = f || function(a,b){ return a > b; };
}

Heap.prototype.put = function(val){
  this.heap.push(val);

  var i = this.heap.length - 1,
      parent = i - 1 >> 1;

  while (i !== 0 && this.isPriority(this.heap[i],this.heap[parent])){
    this.heap[i] = this.heap[parent];
    this.heap[parent] = val;
    i = parent;
    parent = i - 1 >> 1
  }

  return this.heap;
}

Heap.prototype.get = function(val){
  if (this.heap.length === 0){
    return null;
    
  } else if (this.heap.length === 1){
    return this.heap.pop();
  }

  var first = this.heap[0],
      last = this.heap.pop(),
      i = 0;

  this.heap[i] = last;

  while (true){
    var j = 2*i + 1;

    if (this.heap[j] === undefined){
      break;
    }

    if (this.heap[2*i + 2] !== undefined && this.isPriority(this.heap[2*i + 2],this.heap[j])){
      j = 2*i + 2;
    }

    if (this.isPriority(this.heap[j],this.heap[i])){
      this.heap[i] = this.heap[j];
      this.heap[j] = last;
      i = j;
    } else {
      break;
    }
  }

  return first;
}

function makeGraphs(graph){
  // separate disconnected graphs
  var graphs = [],
      index = 0,
      visited = new Set();
      
  function traverse(v){  
    visited.add(v);
    
    var vs = graph.vertices[v];
    
    if (vs.length > 0){
      graphs[index].vertices[v] = [];
    }
    
    for (var i in vs){
      graphs[index].vertices[v].push(vs[i]);
      graphs[index].numEdges++;
      
      if (!visited.has(vs[i])){
        traverse(vs[i]);
      }
    }
  }
  
  for (var i in graph.vertices){
    if (!visited.has(i) && graph.vertices[i].length >0){
      graphs.push({vertices: {}, numEdges: 0});
      traverse(i);
      index++;
    }
  }
  
  // enumerate odd degree vertices and their edges
  for (var i=0; i<graphs.length; i++){
    graphs[i].numEdges /= 2;
  
    graphs[i].numOddDegreeVertices = 0;
    graphs[i].edgesWithOddDegreeVertices = new Set();
  
    for (var u in graphs[i].vertices){
      if (graphs[i].vertices[u].length & 1){
        graphs[i].numOddDegreeVertices++;
        
        graphs[i].vertices[u].forEach(function(v){
          var edge = u + '-' + v;
          
          if (!graphs[i].edgesWithOddDegreeVertices.has(edge) 
           && !graphs[i].edgesWithOddDegreeVertices.has(v+'-'+u)){
            graphs[i].edgesWithOddDegreeVertices.add(edge);
          }
        });
      }    
    }
  }
  
  return graphs;
}

function potentialEdges(graph){
  if (graph.numOddDegreeVertices === 2){
    return graph.numEdges;
  }
  return graph.numEdges - Math.min(2,graph.numOddDegreeVertices);
}

function removeEdge(graph,edge){
  var vertices = edge.split("-"),
      u = vertices[0],
      v = vertices[1];
      
  graph.vertices[u].splice(graph.vertices[u].indexOf(v),1);
  graph.vertices[v].splice(graph.vertices[v].indexOf(u),1);
  graph.edgesWithOddDegreeVertices.delete(edge);
  
  return graph;
}

function hasEulerianPath(graph){
  if (graph.numOddDegreeVertices === 2 || graph.numOddDegreeVertices === 0){
    return true;  
  }
  return false;
}

function copyGraph(graph){
  var copy = {
    vertices: {},
    numEdges: graph.numEdges,
    numOddDegreeVertices: graph.numOddDegreeVertices,
    edgesWithOddDegreeVertices: new Set(graph.edgesWithOddDegreeVertices)
  };
  
  for (var v in graph.vertices){
    copy.vertices[v] = graph.vertices[v].slice();
  }
  
  return copy;
}

function f(ps){
  var edges = [],
      edgeIndexes = {},
      graph = {vertices: {}};
      
  for (var i=0; i<ps.length; i++){
    edgeIndexes[ps[i]] = i;
    edges[i] = ps[i].split("-");
  }
  
  for (var i=0; i<edges.length; i++){  
    if (graph.vertices[edges[i][0]] !== undefined){
      graph.vertices[edges[i][0]].push(edges[i][1]);
      
    } else {
      graph.vertices[edges[i][0]] = [edges[i][1]];
    }
    
    if (graph.vertices[edges[i][1]] !== undefined){
      graph.vertices[edges[i][1]].push(edges[i][0]);
      
    } else {
      graph.vertices[edges[i][1]] = [edges[i][0]];
    }
  }
  
  var heap = new Heap(function(a,b){
    return potentialEdges(a) > potentialEdges(b);
  });
  
  var graphs = makeGraphs(graph);

  for (var i=0; i<graphs.length; i++){
    heap.put(graphs[i]);
  }
  
  var current = heap.get();

  while (current !== null){
    if (current.numEdges > 1 && hasEulerianPath(current)){
      return current;
    }
    
    current.edgesWithOddDegreeVertices.forEach(function(edge){
      var copy = copyGraph(current);

      removeEdge(copy,edge);
      graphs = makeGraphs(copy);
      
      for (var i=0; i<graphs.length; i++){
        heap.put(graphs[i]);
      }
    });
    
    current = heap.get();
  }
 
  return "The longest chain appears to be one edge only.";
}

var input = ['7-4','11-8','11-11','1-0','4-2','7-5','10-8','7-3','10-5','7-2','9-8','12-8','0-0','11-10'];

console.log('Input: ' + input.join(', '));
console.log('---');
console.log('Output: ' + JSON.stringify(f(input)));
console.log('---');
console.log("OP example solution: 12-8, 8-11, 11-11, 11-10, 10-5, 5-7, 7-4, 4-2, 2-7, 7-3");