Простая головоломка R (устранение пар)

Question

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

У меня есть серия целочисленных пар, которые представлены в виде строк в фрейме данных из двух столбцов.Цель состоит из трех частей:

1. Вам необходимо «исключить» все строки в этом фрейме данных.Чтобы «исключить» строку, вы должны выбрать одну из единиц из этой пары и отправить / сохранить ее в векторе «выбранных» элементов.

2. Вы должны найти наименьшее возможноекомбинация «выбранных элементов», которая исключит все пары в кадре данных.

3. Код должен быть вычислительно эффективным, поскольку он будет применяться к довольно большим наборам данных.

Например, можно выбрать элементы «1»и «2» из следующего списка пар:

1   3
1   4
2   5
3   2

Приведенные ниже данные можно использовать в качестве рабочего примера.

Спасибо!

Винсент

---

Обновление для некоторого контекста:

Привет Cipi и SiggyF.

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

Я работаю с данными поперечного сечения временных рядов, в которых N намного больше, чем T. Я хотел бы использовать стандартные ошибки с коррекцией на панели, подобные тем, которые были предложены в Beck & Katz (1995).Пакеты «pcse» в основном способны сделать это просто отлично.Когда у вас есть несбалансированная панель, она по существу создает «прямоугольный» набор данных (каждый блок времени имеет полный объем наблюдений), заполняя пропущенные значения для пропущенных наблюдений в каждой панели.Затем pcse вычисляет матрицу Sigma.hat, которая, по сути, представляет собой средневзвешенное значение внешнего произведения остатков за периоды времени (представьте, что оно усредняется по массиву NXNXT, чтобы привести его к NXN Sigma.hat).

Проблема в том, что если любые две единицы имеют нулевое одновременное наблюдение, то соответствующая ячейка в Sigma. Это будет NA, и pcse не сможет использовать ее для получения сэндвич-оценки ковариации дисперсии.матрица.В моем примере номера фрейма данных соответствуют индексу пропущенных значений в Sigma.hat.Я хочу автоматически обрезать Sigma.hat, чтобы получить оценку VCOV, которая использует максимально возможную информацию, поэтому я хочу сохранить как можно больше чисел в кадре данных.

Это, вероятно, очень непонятно для тех, кто не изучал pcse, но я надеюсь, что вы поняли суть этого.

Извините, что произвел впечатление непристойности, но уверяю вас, это законно.

---

test <-структура (список (ряд = c (27L, 44L, 45L, 111L, 128L, 129L, 195L, 212L, 213L, 279L, 296L, 297L, 363L, 380L, 381L, 7L, 91L, 175L, 259L, 343L, 44L, 45L, 70L, 128L, 129L, 154L, 212L, 213L, 238L, 296L, 297L, 322L, 380L, 381L, 406L, 7L, 37L, 48L, 91L, 121л, 132л, 175л, 205л, 216л, 259л, 289л, 300л, 343л, 373л, 384л, 7л, 37л, 48л, 91л, 175л, 205л, 216л, 259л, 289л, 300л, 343л, 373л, 384L, 44L, 45L, 128L, 129L, 212L, 213L, 296L, 297L, 380L, 381L, 37L, 121L, 205L, 289L, 373L, 27L, 44L, 45L, 111L, 128L, 129L, 195L, 212L, 213L279L, 296L, 297L, 363L, 380L, 381L, 7L, 91L, 175L, 259L, 343L, 44L, 45L, 70L, 128L, 129L, 154L, 212L, 213L, 238L, 296L, 297L, 322L, 380L, 381L, 406L, 7L, 37L, 48L, 91L, 121L, 132L, 175L, 205L, 216L, 259L, 289L, 300L, 343L, 373L, 384L, 7L, 37L, 48L, 91L, 121L, 132L, 175L, 205L, 216L, 259л, 289л, 300л, 343л, 373л, 384л, 44л, 45л, 128л, 129л, 212л, 213л, 296л, 297л, 381л, 37л, 121л, 205л, 289л, 373л, 27л, 44л, 45л, 111л, 128л, 129л, 195л, 212л, 213л, 279л, 296л, 297л, 363л, 380л, 381л, 7л, 91л, 175л, 253л, 44л, 45л, 70л, 128л, 129л, 154л, 212л, 213л, 238л, 296л,297L, 322L, 380L, 381L, 406L, 7L, 37L, 48L, 91L, 121L, 132L, 175L, 205L, 216L, 259L, 289L, 300L, 343L, 373L, 384L, 7L, 37L, 48L, 91L, 121L, 132L, 175 л, 205 л, 216 л, 259 л, 289 л, 300 л, 343L, 373L, 384L, 44L, 45L, 128L, 129L, 212L, 213L, 296L, 297L, 380L, 381L, 37L, 121L, 205L, 289L, 373L, 27L, 44L, 45L, 111L, 128L, 129L, 195L, 212L, 213L, 279L, 296L, 297L, 363L, 380L, 381L, 7L, 91L, 175L, 259L, 343L, 44л, 45л, 70л, 128л, 129л, 154л, 212L, 213L, 238L, 296L, 297L, 322L, 380L, 381L, 406L, 7L, 37L, 48L, 91L, 121L, 132L, 175L, 205L, 216L, 259L, 289L, 300L, 343L, 373L, 384L, 7L, 37L, 48л, 91л, 121л, 132л, 175л, 205л, 216L, 259L, 289L, 300L, 343L, 373L, 384L, 44L, 45L, 128L, 129L, 212L, 213L, 296L, 297L, 380L, 381L, 37L, 121L, 205L, 289L, 373L, 27L, 44L, 45L, 111L, 128L, 129L, 195L, 212L, 213L, 279L, 296L, 297L, 363L, 380L, 381L, 7L, 91L, 175L, 259L, 343L, 44L, 45L, 70L, 128L, 129L, 154L, 212L, 213L, 238L, 296L, 297L, 322L, 380L, 381L, 406L, 7L, 37L, 48L, 91L, 121L, 132 л, 175 л, 205 л, 216 л, 259 л, 289 л, 300л, 343л, 373л, 384л, 7л, 37л, 48л, 91L, 121L, 132L, 175L, 205L, 216L, 259L, 289L, 300L, 343L, 373L, 384L, 44L, 45L, 128L, 129L, 212L, 213L, 296L, 297L, 380L, 381L, 37L, 121L, 205L, 289L, 373L), col = c (7L, 7L, 7L, 7л, 7л, 7л, 7л, 7л, 7л, 7л, 7л, 7л, 7л, 7л, 7л, 27л, 27л, 27л, 27л, 27л, 37L, 37L, 37L, 37L, 37L, 37L, 37L, 37L, 37L, 37L, 37L, 37L, 37L, 37L, 37L, 44L, 44L, 44L, 44L, 44L, 44L, 44л, 44л, 44л, 44л, 44л, 44л, 44л, 44л, 44л, 45л, 45л, 45л, 45л, 45л, 45л, 45л, 45л, 45л, 45л, 45л, 45л, 45л, 45л, 45л, 48л, 48л, 48л, 48л, 48л, 48л, 48л, 48л, 48л, 48л, 70л, 70л, 70л, 70л, 70л, 91л, 91л, 91л, 91L, 91L, 91L, 91L, 91L, 91L, 91L, 91L, 91L, 91L, 91L, 91L, 111L, 111L, 111L, 111L, 111L, 121L, 121L, 121L, 121L, 121L, 121L, 121L, 121L, 121L, 121L, 121L, 121L, 121L, 121L, 121L, 128л, 128л, 128л, 128л, 128л, 128л, 128л, 128л, 128л, 128л, 128л, 128л, 128л, 128л, 128л, 129л, 129л, 129л, 129L, 129L, 129L, 129L, 129L, 129L, 129L, 129L, 129L, 129L, 129L, 129L, 132 л, 132 л, 132 л, 132 л, 132 л, 132 л, 132 л, 132 л, 132 л, 132 л, 154 л, 154 л, 154L, 154L, 154L, 175L, 175L, 175L, 175 л, 175 л, 175 л, 175 л, 175 л, 175 л, 175 л, 175 л, 175 л, 175 л, 175 л, 175 л, 195L, 195L, 195L, 195L, 195L, 205L, 205L, 205L, 205L, 205L, 205L, 205L, 205L, 205L, 205L, 205L, 205L, 205L, 205L, 205L, 212L, 212L, 212L, 212L, 212L, 212L, 212L, 212L, 212L, 212L, 212L, 212L, 212L, 212L, 212L, 213L, 213L, 213L, 213L, 213L, 213L, 213L, 213L, 213L, 213L, 213L, 213L, 213L, 213L, 213L, 216L, 216L, 216L, 216L, 216L, 216L, 216L, 216L, 216L, 216L, 238L, 238L, 238L, 238L, 238L, 259L, 259L, 259L, 259L, 259L, 259L, 259L, 259L, 259L, 259L, 259L, 259L, 259L, 259L, 259L, 279L, 279L, 279L, 279L, 279L, 289L, 289L, 289L, 289L, 289L, 289L, 289L, 289L, 289L, 289L, 289L, 289L, 289L, 289L, 289L, 296L, 296L, 296L, 296L, 296L, 296L, 296L, 296L, 296L, 296L, 296L, 296L, 296L, 296L, 296L, 297L, 297L, 297L, 297L, 297L, 297L, 297L, 297L, 297L, 297L, 297L, 297L, 297L, 297L, 297L, 300L, 300L, 300л, 300л, 300л, 300л, 300л, 300л, 300л, 300л, 322л, 322л, 322л, 322л, 322L, 343L, 343L, 343L, 343L, 343L, 343L, 343L, 343L, 343L, 343L, 343L, 343L, 343L, 343L, 343L, 363L, 363L, 363L, 363L, 363L, 373L, 373L, 373L, 373L, 373L, 373L, 373L, 373L, 373L, 373L, 373L, 373L, 373L, 373L, 373L, 380л, 380л, 380л, 380л, 380л, 380л, 380л, 380л, 380л, 380л, 380л, 380л, 380л, 380л, 380л, 381л, 381л, 381л, 381L, 381L, 381L, 381L, 381L, 381L, 381L, 381L, 381L, 381L, 381L, 381L, 384L, 384L, 384L, 384L, 384L, 384L, 384L, 384L, 384L, 384L, 406L, 406L, 406L, 406L, 406L)), .Names = c ("строка", "col"), row.names = c (NA, -400L), class = "data.frame") </p>

Answer 1

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

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

good <- function(dat, result = NULL) {
 sampr <- dat[sample(1:(dim(dat)[1]),1),]
 if (dim(dat)[1] == 0){
    result
  } else {
    good(subset(dat, row != sampr$row & row != sampr$col & col != sampr$row & 
                     col != sampr$col),result = c(result, sampr$row, sampr$col))
  }
}

Я бы запускал это несколько раз и оставлял лучший. (Также может быть полезно отслеживать размер наихудшего, так как он дает нижнюю границу для оптимального размера). Может быть полезно постобработать результат, чтобы удалить лишние вершины.

Выполнение 10000 итераций (и удаление избыточных вершин) дает следующее решение из 19 элементов вашей типовой задачи.

7 37 45 48 91 121 128 132 175 205 212 216 259 279 289 300 343 373 384

Мы также знаем, что оптимальное решение должно иметь не менее 15 вершин.