Подскажите алгоритм

[Yen]

Помогите, пожайлуста, составить алгоритм!
Ящик имеет n х n ячеек для бутылок с молоком. Мистер Смит для каждого столбца и каждой строки заготовил отдельный листок бумаги, где записал наличие или отсутствие в ячейке бутылки молока: 1 — ячейка занята молоком, 0 — ячейка не занята молоком, но забыл проставить на каждом листе чему он соответствует: строке или столбцу и все это вложил в коробку. В пути ящик попал под дождь, и часть записей на листах пропала. Испорченные цифры 1 и 0 были заменены цифрой 2. Определить, какие записи относятся к строкам, а какие — к столбцам. Исходные испорченные записи по строкам и столбцам задаются в текстовом файле. Результаты сохранить в текстовом файле.
Пример:
Исходные данные
1) 01210
2) 21120
3) 21001
4) 12110
5) 12101
6) 12101
7) 00011
8) 22222
9) 11001
10) 10010
Восстановленные данные
№4) 1) 10) 7) 5)
6) 1 0 1 0 1
9) 1 1 0 0 1
3) 1 1 0 0 1
2) 1 1 1 1 0
8) 0 0 0 1 1

Кроме жуткого перебора ничего придумать не могу

[нг]

переношу.

[незваный гость]

Ну, не так страшен перебор, как его малюют. Если вести аккуратную бухгалтерию, то он может получится вполне эффективным. Например так:

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

Должно работать довольно шустро…

P.S. И действительно работает довольно шустро. В контрольном примере находит первое решение, перебрав 28 частично заполненных набора. Находит все 604 решения, исследовав 2156 наборов. Это малая доля от 3,628,800. Вся программа — около 130 строк на Python.

[Yen]

Спасибо большое за идею!
А имеет ли какое-нибудь значение с какой строки/колонки начинать перебор(в самом начале)?
И как все это дело реализовать программно? Подскажите хотя бы основы программы ( буду рада даже псевдокоду )

[незваный гость]

Yen писал(а):

А имеет ли какое-нибудь значение с какой строки/колонки начинать перебор(в самом начале)?

Смотря для чего. Для правильного решения — нет. Для того, в каком порядке Вы найдете решения — да.

Yen писал(а):

Подскажите хотя бы основы программы ( буду рада даже псевдокоду Rolling Eyes )

Разбирайтесь. Python 2.5 (и даже несколько комментариев):

"""
http://uweb.txstate.edu/~ch01/prob96sh.htm

1996-1997 Asia Regional ACM International Collegiate Programming Contest
Shanghai University, Shanghai, P. R. China,
Nov. 3, 1996

Problem D
Milk Bottle Data

Input file: bottle.in

There is a box of the shape of an N*N lattice. Each grid of the lattice may
contain a milk bottle or none. Mr. Smith wrote down the data of the box by
making a record for each row from left to right and each column from top to
bottom. In each record, '1'indicaes that there is a bottle in the
corresponding grid and '0'does not. Unfortunately, the order of these records
is thrown into confusion, and some of these records have corrupted.

Now it's up to you to provide a program to recover these data:

i.e. to give the original arrangement of the box and give real values for
those corrupted data.

Input

The input data is stored in file BOTTLE.IN, where '2' denotes that the
corresponding character has been corrupted. Each line in the file represents
a record. You should output the original arrangement of the box, and show the
record number for each column on the top of the lattice, and show the record
number for each row to the left of the lattice.

Output

You are required to give only one possible result if there are many, and you
should give an indication if there is no possibility of original arrangement.

Sample Input

01210
21120
21001
12110
12101
12101
00011
22222
11001
10010

Output for the Sample Input

9 8 6 2 7
4 1 0 1 1 0
10 1 0 0 1 0
1 0 1 1 1 0
3 0 1 0 0 1
5 1 1 1 0 1
"""

class SolvedException(Exception):
  def __init__(self):
    Exception.__init__(self)

class Solver:
  def __init__(self):
    self.N = None
    self.lines = None
    self.found = None
    self.positions = None
    self.rawpos = None

  def loadFile(self, fn):
    f = open(fn, "r")
    lines = f.read().split("\n")
    f.close()
    if lines[-1] == "": del lines[-1]
    assert(len(lines) & 1 == 0)
    self.N = len(lines) // 2
    self.lines = []
    for l in lines:
      assert(len(l) == self.N)
      ll = [int(ch) for ch in l if ch in ['0', '1', '2']]
      assert(len(ll) == self.N)
      self.lines.append(ll)

  def solve(self, fn):
    self.loadFile(fn)
    ## first rows, then cols
    rowscols = [set(range(2*self.N)) for ix in range(2*self.N)]
    availRC = set(range(2*self.N))
    self.found = 0; self.positions = 0; self.rawpos = 0
    try:
      self.solver(availRC, rowscols)
    except SolvedException: ## expected when a solution found
      pass
    if self.found == 0:
      print "nothing found"
    else:
      print "found %d variant(s)" % self.found
    print "%d position(s) checked" % self.positions
    print "%d raw position(s) checked" % self.rawpos

  def printSolution(self, rowscols):
    rows = [tuple(rowscols[ix])[0] for ix in range(self.N)]
    cols = [tuple(rowscols[ix])[0] for ix in range(self.N, 2*self.N)]

    print " ".join([str(c+1) for c in cols])
    lattice = [[" "] * self.N for ix in range(self.N)]
    for r in range(self.N):
      lno = rows[r]
      for c in range(self.N):
        lattice[r][c] = str(self.lines[lno][c])
    for c in range(self.N):
      lno = cols[c]
      for r in range(self.N):
        ch1 = lattice[r][c]
        ch2 = str(self.lines[lno][r])
        if ch1 == "2":
          lattice[r][c] = ch2
        elif ch2 != "2":
          assert(ch1 == ch2) ## verification
    for r in range(self.N):
      print rows[r]+1, " ".join(lattice[r])
    print
    self.found += 1

    # raise SolvedException(); ## found, nothing more to do

  def solver(self, availRC, rowscols):
    self.positions += 1
    mrc = None; mv = 2*self.N + 1
    for rc in availRC:
      if len(rowscols[rc]) < mv:
        mrc = rc; mv = len(rowscols[rc])
    # we will assign mrc all possible lines
    for lno in rowscols[mrc]:
      self.assign(mrc, lno, availRC, rowscols)

  def assign(self, rc, lno, availRC, rowscols):
    ## queue is a set, because if it contains more than one entry
    ## it can be inserted twice
    queue = set([(rc, lno)])
    ## we make a copy (so we can backtrack)
    newRC = set(availRC); newrowscols = [set(x) for x in rowscols]
    while queue:
      self.rawpos += 1
      rc, lno = queue.pop()
      newRC.remove(rc)
      newrowscols[rc] = set([lno])
      for xrc in newRC:
        newrowscols[xrc].discard(lno)
        if (rc < self.N) != (xrc < self.N):  ## if rc crosses xrc
          for xlno in tuple(newrowscols[xrc]):
            ## checking if lno in rc is compatible with xlno in xrc
            ch1 = self.lines[lno][xrc % self.N]
            ch2 = self.lines[xlno][rc % self.N]
            if ch1 != 2 and ch2 != 2 and ch1 != ch2:
              newrowscols[xrc].remove(xlno)
        l = len(newrowscols[xrc])
        if l == 0: return
        if l == 1:
          queue.add((xrc, tuple(newrowscols[xrc])[0]))
    if newRC:
      self.solver(newRC, newrowscols)
    else:
      self.printSolution(newrowscols)

if __name__ == "__main__":
  Solver().solve("milk-bottles.in")

[sadomovalex]

Yen
надо исходить из следующих соображений. Пусть $x_i$ - число записанное в i-й строке исходных данных; $N_i$ - количество неопределенностей в $x_i$ (например, в Вашем наборе $N_1=1, N_2=2,N_3=1,\ldots$); $N=\sum\limits_{i=1}^{2n}N_i$ - всего неопределенностей в исходных данных. Тогда существует $2^N$ вариантов раскрытия неопределенностей. При этом для каждого уже определенного варианта из $2n$ строк нужно определить такое сочетание $n$ строк, при котором оставшиеся $n$ строк будут являться столбцами матрицы, составленной из первых. Всего таких сочетаний $C_{2n}^n$. Вот эту последнюю задачу и можно решать методом, который предложил незваный гость. Всего получается $2^NC_{2n}^n$ вариантов (для указанных исходных данных = 1032192)

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

[незваный гость]

sadomovalex,
«надо» — это сильно. Наверное, правильнее сказать «можно». Но давайте дойдем до конца. Вы доопределили данные ($2^N$ способами), поделили их на строки/колонки, ($C_{2n}^n$), теперь надо строки и колонки переставлять, не правда ли? Получаем $2^N (2n)!$.

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

sadomovalex писал(а):

в Вашем методе учитывается, что строки могут стоять на разных местах?

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

Кроме того, мы не пытаемся угадывать, чему равны двойки. Скорее мы рассматриваем кортежи как сопоставление с регулярным выражением (а двойки — как вайлдкард). Поэтому в некоторых конфигурациях двойки остаются в ответе: значение в матрице не определено.

  5 6 3 X 1
4 1 1 1 1 0
8 2 2 1 0 1
9 1 1 0 0 1
7 0 0 0 1 1
2 1 1 1 0 0

Для больших задач можно было бы попробовать пару оптимизаций: (а) кодирование кортежей ($0 \to -1$, $1 \to 1$, $2 \to 0$), тогда сопоставление превращается в $ a * b \geqslant 0 $, и (б) вычисление совместимости кортежей до начала перебора ($\Theta(N^4)$, по скорости и памяти, зато уходит цикл в переборе).

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

[sadomovalex]

незваный гость писал(а):

Но давайте дойдем до конца. Вы доопределили данные ($2^N$ способами), поделили их на строки/колонки, ($C_{2n}^n$), теперь надо строки и колонки переставлять, не правда ли? Получаем $2^N (2n)!$.

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

Цитата:

Для больших задач можно было бы попробовать пару оптимизаций: (а) кодирование кортежей ($0 \to -1$, $1 \to 1$, $2 \to 0$), тогда сопоставление превращается в $ a * b \geqslant 0 $, и (б) вычисление совместимости кортежей до начала перебора ($\Theta(N^4)$, по скорости и памяти, зато уходит цикл в переборе).

что есть a и b? интересуюсь, потому что меня более интересуют решения этой задачи в более компактной форме без перебора, либо с минимальным перебором

[незваный гость]

sadomovalex писал(а):

что есть a и b?

Сопоставляемые значения (на пересечении колонки и строки). Идея в том, что мы имеем дело с таблицей (0 сопоставляется с 0 или 2, 1 — с 1 или 2, 2 с 0, 1, и 2). А после написанного преобразования наша таблица сводится к указанной формуле.

Я полагаю, что возможны и другие варианты оптимизации сопоставления. Искать вот зачем? Задача решается при N=10 за вполне приемлемое время, рост скорости примерно экспоненциальный, так чего еще желать? (Задача-то олимпиадная, а не из жизни.)

Добавлено спустя 8 минут 29 секунд:

sadomovalex писал(а):

не совсем..

Договорились! $2^N \frac{(2n)!}{n!}$ умножить на что-то (поскольку эффективного способа решать, как расположить оставшиеся $n$ кортежей в колонки нет).

Добавлено спустя 8 минут 43 секунды:

Совсем другой подход: для каждой клетки матрицы ($\Theta(N^2)$) найдем множества тех кортежей, которые могут стоять там как строки, и как колонки (это два разных множества)). Соответственно, кортеж может стоять в строколонке, если он может стоять в любой из клеток строколонки. Можно пытаться обдумать, можно ли извлечь из этого алгоритм…

[sadomovalex]

незваный гость писал(а):

:evil:
Договорились! $2^N \frac{(2n)!}{n!}$ умножить на что-то (поскольку эффективного способа решать, как расположить оставшиеся $n$ кортежей в колонки нет).

согласен - конечно, здесь порядок важен и поэтому нужно брать не сочетания, а размещения, т.е. получаем $O(2^NA_{2n}^n)=O(2^N\frac{(2n)!}{n!})$

[coerbi]

Проконтролируйте, пожалуйста, если в чем-то неправильно понял ход Ваших мыслей:
1-ый шаг) Раскрыть неопределенность (заменить двойки на 0 или 1). Соответственно объем входных данных увеличивается.

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

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

4) Если облом, переключиться первым кортежем на место второй (3-ей...5-ой) строки в итоговой таблице и повторять шаг (3).

Все ли я правильно понял..

[незваный гость]

Вы имеете в виду мой подход или sadomovalex? Я нигде неопределенностей не раскрываю. Кроме того, я иначе организовываю перебор с возвратами.

[coerbi]

Цитата:

Вы имеете в виду мой подход или sadomovalex?

гм...по-моему больше похоже на подход sadomovalex. Мне просто интересно: имеет ли право на существование описанный мною алгоритм или он принципиально не верен???
( по специальности я - не программист )

[sadomovalex]

coerbi писал(а):

гм...по-моему больше похоже на подход sadomovalex. Мне просто интересно: имеет ли право на существование описанный мною алгоритм или он принципиально не верен???
( по специальности я - не программист )

да, здесь больше на мой подход похоже. Но мне кажется, что его алгоритмизировать будет сложнее. Для кортежа, вставленного в очередную строку (1-ю, 2-ю, ...), может подойти несколько вариантов расположения столбцов, и поэтому для нахождения всех решений это нужно будет учитывать. Опять же для нахождения всех решений нужно описаную процедуру повторить для всех кортежей (в пределах текущего определенного списка) - но в этом случае решения будут повторяться.
Вот набросал программку на C++, находящую все возможные варианты расположения кортежей:

// Печатает очередное размещение элементов массива tuple_ind
void print_placement(const int tuple_ind[], const int ind[], const int num)
{
    for (int i = 0; i < num; ++i)
        printf("%d ", tuple_ind[ind[i]]);
    printf("\n");
}

// Находит очередное размещение из total_num элементов по num элементам массива tuple_ind
void placement_impl(const int tuple_ind[], const int total_num, const int num,
                        int ind[], int current_place)
{
    if (current_place == num)
    {
        print_placement(tuple_ind, ind, num);
        return;
    }
    
    for (int i = 0; i < total_num; ++i)
    {
        bool already_placed = false;
        for (int j = 0; j < current_place; ++j)
        {
            if (i == ind[j])
            {
                already_placed = true;
                break;
            }
        }

        if (already_placed)
            continue;

        ind[current_place] = i;
        placement_impl(tuple_ind, total_num, num, ind, current_place + 1);
    }
}

// Находит все размещения из total_num элементов по num элементам массива tuple_ind
void placement(const int tuple_ind[], const int total_num, const int num)
{
    int* ind = new int[num];
    placement_impl(tuple_ind, total_num, num, ind, 0);
    delete [] ind;
}

int main()
{
    // массив индексов входных кортежей
    int tuple_ind[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    placement(tuple_ind, sizeof(tuple_ind)/sizeof(tuple_ind[0]), 5);

   return 0;
}

Для исходных данных с $2n=10$ печатает $\frac{10!}{5!}=30240$ вариантов

[pavlik888888]

привет всем....если не секрет кто нибудь ее на с ++ написал?если да,можете текст скопировать,хоть посмотреть где затупил?просто я в ней что то с реккурсиями запутался....