Число последовательных выборок из 2-мерного массивв

[upgrade]

Для натурального ряда длиной $m$ число всех возможных последовательных выборок (в последовательности чисел следующее число больше предыдущего на единицу)
$k=\frac {m(m+1)}{2}$
Для натурального двумерного массива (по горизонтали натуральный ряд и по вертикали натуральный ряд)
Число возможных аналогичных "двумерных" объектов - просто умножаем на такое же количество по вертикали (длиной ряда по вертикали $n$)?:
$k=\frac {m(m+1)}{2}\cdot \frac {n(n+1)}{2} $

[Someone]

Что Вы понимаете под "последовательными выборками"? Есть выборки с повторениями и выборки без повторений. Есть выборки упорядоченные и выборки неупорядоченные.

[grizzly]

Someone в сообщении #1305238 писал(а):

Что Вы понимаете под "последовательными выборками"?

Думаю, что под одной "последовательной выборкой" понимается отрезок $[a,b]\subset \mathbb N$, $a,b \in \mathbb N, 1\le a\le b \le m$.

[upgrade]

Someone
grizzly
Выборки из ряда элементов, стоящих друг за другом под номерами
$1,2,3,4,5,6,7,...n$

$1$ элемент это могут быть элементы под номерами $1;2;3;4;5;...$
$2$ элемента - $\{1,2\}$; $\{2,3\}$; $\{3,4\}$ ...
$3$ элемента - $\{1,2,3\}$; $\{2,3,4\}$; $\{3,4,5\}$ ...
...
для "двумерного" ряда элементов
$a,b,c,d,e,f,g,...z$
$\alpha,\beta,\gamma,\delta,\varepsilon,\zeta,\eta,...\omega$

выбираем по одному элементу один за другим:
$\{a\},\{b\},\{c\},\{d\},\{e\},\{f\},\{g\},...$
$\{\alpha\},\{\beta\},\{\gamma\},\{\delta\},\{\varepsilon\},\{\zeta\},\{\eta\},...$

выбираем по два элемента один за другим "верх" и "вправо"
$\{a,b\};\{b,c\};\{c,d\};\{d,e\};\{e,f\}...$
$\{\alpha,\beta\};\{\beta,\gamma\};\{\gamma,\delta\};\{\delta,\varepsilon\};\{\varepsilon,\zeta\};...$
$\{a,\alpha\};\{b,\beta\};\{c,\gamma\};\{d,\delta\};\{e,\varepsilon\}...$
дальше для этой выборки не уверен, верно ли выбрать "прямоугольнички"
$\{a,b,\alpha,\beta\};\{b,c\,\beta,\gamma\};\{c,d\,\gamma,\delta\}...$

[provincialka]

upgrade в сообщении #1305353 писал(а):

дальше для этой выборки не уверен, верно ли выбрать "прямоугольнички"

А кто задачу ставит? Вы сами или кто-то другой? Из книжки? Из другой задачи?

[upgrade]

provincialka в сообщении #1305436 писал(а):

А кто задачу ставит? Вы сами или кто-то другой? Из книжки? Из другой задачи?

Задача из практики - необходимо найти два множества с одинаковыми элементами и одинаковой структурой их расположения.
Идея решения - поиск "кусочков" одного множества в других.
Одномерная решается просто. Захотелось понять как быстро растет число выборок с ростом размерности.

[Yodine]

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

-- 19.04.2018, 06:42 --

В целом, вам надо понять, как вы собираетесь упорядочивать кортежи, ввести функцию порядка. Как введете, так можно искать подстроки. Но наверняка вам надо что-то иное. ))

[upgrade]

Yodine в сообщении #1305466 писал(а):

Для одномерного случая это задача поиска подстроки.

Всех подстрок и количества этих подстрок.

Yodine в сообщении #1305466 писал(а):

А для двумерного я так и не понял, что вам требуется, какие подстроки допустимы, какие, нет.

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

[Yodine]

upgrade Похоже вам требуются n-мерные параллелепипеды. Для двумерного случая соответственно прямоугольники.
Невнимательно прочел ваше сообщение.
В общем случае это видимо изоморфизм графов с поименованными вершинами. По сути перечисление графов с поименованнными вершинами и их сравнение.

-- 19.04.2018, 08:15 --

https://ru.wikipedia.org/wiki/Задача_поиска_изоморфного_подграфа
Ваша задача вероятно немного проще, поскольку вершины поименованы, имхо. Похоже, что быстрее можно находить, сокращать пространство поиска.

-- 19.04.2018, 08:20 --

И рост вашего числа это что-то вроде последовательность A001187 в OEIS.
https://ru.wikipedia.org/wiki/Перечисление_графов
Там не совсем ваша задача видимо, нечто похожее.

[arseniiv]

upgrade в сообщении #1305353 писал(а):

для "двумерного" ряда элементов
$a,b,c,d,e,f,g,...z$
$\alpha,\beta,\gamma,\delta,\varepsilon,\zeta,\eta,...\omega$

И где же тут двумерность?

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

[upgrade]

arseniiv в сообщении #1305681 писал(а):

И где же тут двумерность?

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

arseniiv в сообщении #1305681 писал(а):

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

Меня это сбивало с толку.

[arseniiv]

upgrade в сообщении #1306070 писал(а):

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

Погодите, как так четыре, когда три? Например, у буквы из верхней строки соседи слева, справа и снизу.

[upgrade]

arseniiv в сообщении #1306269 писал(а):

Погодите, как так четыре, когда три? Например, у буквы из верхней строки соседи слева, справа и снизу.

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

[arseniiv]

В общем, я так понимаю, у вас всё же некоторые значения, индексированные двумя числами:

$$\begin{matrix} a_{11}, & a_{12}, & a_{13}, & \ldots \\ a_{21}, & a_{22}, & a_{23}, & \ldots \\ a_{31}, & a_{32}, & a_{33}, & \ldots \\ \ldots & & & \end{matrix}$$

А то вы не очень-то понятно сначала описали. В будущем это описывать можно очень просто: последовательность $a_1,\ldots$ элементов множества $A$ есть просто некоторая функция $a\colon\mathbb N\to A$, так что «$n$-мерная последовательность» элементов из $A$ есть функция $a\colon\mathbb N^n\to A$. Для конечных вместо соответствующих копий $\mathbb N$ берутся его начальные отрезки.

Возвращаясь к исходной теме, какой угодно многомерный массив можно развернуть в линейный, так что все комбинаторные числа, никак не зависящие от нахождения элементов, скажем, в одинаковых строках или столбцах, будут такими же как для развёрнутого.