Поиск элемента по номеру строки и столбца

[Alex Fox]

Здравствуйте, никак не могу подступиться к решению одной задачи. Есть таблица, состоящая из $n$ столбцов и набор из $m$ пронумерованных элементов (например чисел от 0 до $m$). Из них строится следующий массив (для примера взял $n=3$, $m=3$):
0 0 0
0 0 1
0 0 2
0 0 3
0 1 1
0 1 2
0 1 3
0 2 2
0 2 3
0 3 3
1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3
Из этой таблицы видно, что тут выписаны все сочетания с повторениями (для данных $n$ и $m$). Задача состоит в том, чтобы по номеру строки $i$ и столбца $j$, уметь находить то, какой элемент стоит на пересечении $i$-й строки и $j$-го столбца, для произвольных $n$ и $m$. Существует ли решение для данной задачи? Если да, то как к нему придти?

[DeBill]

Alex Fox
Явных формул, боюсь, мы не получим.
Но "подступиться" можно, например, так.
Пусть $C_{n,m}$ количество строчек в вашей таблице.
Посмотрим на таблицу внимательно: шо мы видим?
Есть куча строчек, где первая цифра - 0, и есть еще куча - где не 0.
Сколько чисел в первой куче? Написав на первом месте 0, мы получили точно такую же задачу, токо с меньшим $n$.
Сколько - во второй? Если низя на первом (и на последующих) месте писать 0, а все остальное моно - дык это опять такая же задача, но с меньшим $m$. И что-то это сильно напоминает... Ба, да это ж треугольник Паскаля! Его элементы - биноминальные к-ты.
Ой, надо же , $C_{n,m} = C^n_{m+n}$, как и должно было быть для сочетаний с повторениями.
Давайте только считать наш тр-к прямоугольным...Повернем его, и уложим на первый квадрант клетчатой плоскости.
Нумерация клеточек: от 0 до...по горизонтали, и такая же - по вертикали.
Пусть $N$ номер строчки таблицы, в которой мы хотим записать число, $M=C_{n,m}$ - общее кол-во чисел в таблице, число $M$ стоит в клетке с номерами $(n,m)$. Ясно, что должно быть $N\leqslant M$. Число $M$ равно сумме двух: левого $L$, и нижнего $D$ соседей. Пусть $X=M-N$.
Будем идти из $M$ по столбцу вниз, пока не встретим число, меньшее $X$. Тут мы затормозим; количество сделанных шагов и есть искомый первый символ. Далее надо пересчет, рекурсия, и т.д.
Т.е., алгоритм вполне реализуем; бин. к-ты можно считать последовательно, сложность алгоритма - порядка $mn$.

[arseniiv]

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

[Alex Fox]

Цитата:

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

Этот момент не понятен. Каким именно образом необходимо повернуть и уложить треугольник?

Цитата:

Пусть $N$ номер строчки таблицы, в которой мы хотим записать число, $M=C_{n,m}$ - общее кол-во чисел в таблице, число $M$ стоит в клетке с номерами $(n,m)$.

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

[svv]

Alex Fox
Привязаны ли Вы к конкретному способу нумерации сочетаний, или подойдёт любой хороший? У меня есть лучше.
Есть смысл использовать универсальный порядок нумерации, не зависящий от $n$. (Хотелось бы также, чтобы он не зависел и от $m$, но такого, наверное, нет.) Вот он для $m=3$, в оффтопе:

(Оффтоп)

0 0 0
0 0 1
0 1 1
1 1 1
0 0 2
0 1 2
1 1 2
0 2 2
1 2 2
2 2 2
0 0 3
0 1 3
1 1 3
0 2 3
1 2 3
2 2 3
0 3 3
1 3 3
2 3 3
3 3 3
0 0 4
0 1 4
1 1 4
0 2 4
1 2 4
2 2 4
0 3 4
1 3 4
2 3 4
3 3 4
0 4 4
1 4 4
2 4 4
3 4 4
4 4 4
...

Здесь перечислены все сочетания с повторениями для $n=4$. Чтобы перечислить все для $n=5,6,7...$, нужно добавить новые элементы по очевидному алгоритму, но, что важно, при этом не изменится нумерация уже выписанных элементов. Таким образом, $n$ в окончательную формулу/алгоритм входить не будет.

[DeBill]

Alex Fox в сообщении #1099864 писал(а):

тот момент не понятен.

Треугольник Паскаля, как его рисуют в книжках, не очень удобен. Удобнее его считать - совпадающим с первым квадрантом плоскости. Порежем квадрант на единичные квадратики. Нумерация столбцов и строк - от 0. Заполним клетки числами: в нижней строке (ее номер - 0) и в самом левом столбце (он так же имеет номер 0) напишем 1. Все остальные клетки заполним по правилу: число в клетке равно сумме двух своих сосоедей - слева и снизу). Это и будет тр-к Паскаля. Хорошо известно, что число, стоящее на пересечении $n$ - го столбца и $k-$ й строки есть биноминальный к-т $C^n_{n+k} = C^k_{n+k}$.

Alex Fox в сообщении #1099864 писал(а):

таблице идет речь? Об исходной

Да.

Видимо, я переборщил, пытаясь уже и алгоритм некий предложить. Давайте отыграем назад: бог с ним, с тр-ком, разберем лишь идею решения, а алгоритм Вы сочините такой, как вам нравится.
Мы имеем (в Ваших обозначениях) таблицу из $ C^m_{m+n}$ строчек. В этой таблице, в первых $C^m_{m+n-1}$ строчках, первый символ равен 0, в остальных (их $C^{m-1}_{m+n-1}$) первый символ не равен 0. Если вы хотите заполнить строчку с номером $N$, то можно делать так: при N $\leqslant C^m_{m+n-1} $ первый символ - 0. Напишем его, после этого получилась такая же задача, только $n$ уменьшилось на 1. Если же $N > C^m_{m+n-1}$, то первый символ (да и все последующие) - не 0. Заменяем ваше $N$ на $N - C^m_{m+n-1}$ - и получаем такую же задачу, но с меньшим (на 1) числом $m$.

[Skeptic]

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

[Alex Fox]

svv в сообщении #1099958 писал(а):

Привязаны ли Вы к конкретному способу нумерации сочетаний, или подойдёт любой хороший? У меня есть лучше.

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

Цитата:

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

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

Цитата:

Пусть $N$ номер строчки таблицы, в которой мы хотим записать число, $M=C_{n,m}$ - общее кол-во чисел в таблице

$C_{n,m}$ - это количество строк в таблице, почему тогда вы пишите, что это количество числе в таблице?

[svv]

Alex Fox в сообщении #1100387 писал(а):

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

В принципе, это не мешает, при желании, воспользоваться «универсальной нумерацией». Ваша получается из моей, если изменить порядок следования столбцов на обратный, изменить порядок следования строк на обратный, и заменить каждое число $d$ в таблице на $n-d$.

[Alex Fox]

svv в сообщении #1099958 писал(а):

Здесь перечислены все сочетания с повторениями для $n=4$. Чтобы перечислить все для $n=5,6,7...$, нужно добавить новые элементы по очевидному алгоритму, но, что важно, при этом не изменится нумерация уже выписанных элементов. Таким образом, $n$ в окончательную формулу/алгоритм входить не будет.

Количество столбцов тоже произвольно, я лишь для примера выбрал $m=3$

[svv]

Да, я это учитываю, у меня тоже $m=3$ только для примера. Для $m=4$ будет другая таблица, бесконечная по вертикали, и тоже для всех $n$ сразу.

[Alex Fox]

svv в сообщении #1100392 писал(а):

Да, я это учитываю, у меня тоже $m=3$ только для примера. Для $m=4$ будет другая таблица, бесконечная по вертикали, и тоже для всех $n$ сразу.

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

[svv]

А каковы типичные значения $m$ и $n$ ?

[Alex Fox]

Типичных значений нет, чем больше тем лучше

[svv]

Формулу, в принципе, можно написать. Она будет рекуррентной, вот в каком смысле: вычисление $d_{i,j}$ (стоящего в $i$-й строке и $j$-м столбце) опирается на найденное ранее $d_{i, j-1}$ (в той же строке) и так далее. Кроме того, там будет использоваться не совсем обычная функция, которую можно назвать «обратный биномиальный коэффициент», дающая $n$ по известному $C^m_{n+m}$ и $m$, или что-то вроде этого. Если такое подойдёт, могу подумать в этом направлении.