2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Число последовательных выборок из 2-мерного массивв
Сообщение17.04.2018, 23:35 


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

 Профиль  
                  
 
 Re: Число последовательных выборок из 2-мерного массивв
Сообщение18.04.2018, 11:06 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Число последовательных выборок из 2-мерного массивв
Сообщение18.04.2018, 11:43 
Заслуженный участник
Аватара пользователя


09/09/14
6093
Someone в сообщении #1305238 писал(а):
Что Вы понимаете под "последовательными выборками"?
Думаю, что под одной "последовательной выборкой" понимается отрезок $[a,b]\subset \mathbb N$, $a,b \in \mathbb N, 1\le a\le b \le m$.

 Профиль  
                  
 
 Re: Число последовательных выборок из 2-мерного массивв
Сообщение18.04.2018, 18:15 


07/08/14
2910
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\}...$

 Профиль  
                  
 
 Re: Число последовательных выборок из 2-мерного массивв
Сообщение19.04.2018, 00:27 
Заслуженный участник
Аватара пользователя


18/01/13
11781
Казань
upgrade в сообщении #1305353 писал(а):
дальше для этой выборки не уверен, верно ли выбрать "прямоугольнички"

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

 Профиль  
                  
 
 Re: Число последовательных выборок из 2-мерного массивв
Сообщение19.04.2018, 09:12 


07/08/14
2910
provincialka в сообщении #1305436 писал(а):
А кто задачу ставит? Вы сами или кто-то другой? Из книжки? Из другой задачи?

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

 Профиль  
                  
 
 Re: Число последовательных выборок из 2-мерного массивв
Сообщение19.04.2018, 09:38 


12/08/14

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

-- 19.04.2018, 06:42 --

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

 Профиль  
                  
 
 Re: Число последовательных выборок из 2-мерного массивв
Сообщение19.04.2018, 09:54 


07/08/14
2910
Yodine в сообщении #1305466 писал(а):
Для одномерного случая это задача поиска подстроки.
Всех подстрок и количества этих подстрок.
Yodine в сообщении #1305466 писал(а):
А для двумерного я так и не понял, что вам требуется, какие подстроки допустимы, какие, нет.
Тоже самое, только не одно измерение, т.е. прямоугольнички таки искать тоже.
Как это в общем виде формулируется (не только прямоугольники, а любые структуры внутри множества, т.е. видимо что-то из теории графов), понятия не имею.

 Профиль  
                  
 
 Re: Число последовательных выборок из 2-мерного массивв
Сообщение19.04.2018, 10:58 


12/08/14

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

-- 19.04.2018, 08:15 --

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

-- 19.04.2018, 08:20 --

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

 Профиль  
                  
 
 Re: Число последовательных выборок из 2-мерного массивв
Сообщение19.04.2018, 22:52 
Заслуженный участник
Аватара пользователя


27/04/09
24309
Уфа
upgrade в сообщении #1305353 писал(а):
для "двумерного" ряда элементов
$a,b,c,d,e,f,g,...z$
$\alpha,\beta,\gamma,\delta,\varepsilon,\zeta,\eta,...\omega$
И где же тут двумерность?

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

 Профиль  
                  
 
 Re: Число последовательных выборок из 2-мерного массивв
Сообщение21.04.2018, 09:49 


07/08/14
2910
arseniiv в сообщении #1305681 писал(а):
И где же тут двумерность?
При таком расположении у каждого элемента может быть максимум четыре соседа. Если ряд "одномерный" то максимум два, из текущего элемента можно получить не два, а четыре, ну т.е. плюсики например ставить не только справа слева, но и вверху внизу.
arseniiv в сообщении #1305681 писал(а):
И, честно говоря, вы могли бы не перечислять все буквы, а использовать (числовые) индексы.
Меня это сбивало с толку.

 Профиль  
                  
 
 Re: Число последовательных выборок из 2-мерного массивв
Сообщение21.04.2018, 23:52 
Заслуженный участник
Аватара пользователя


27/04/09
24309
Уфа
upgrade в сообщении #1306070 писал(а):
При таком расположении у каждого элемента может быть максимум четыре соседа.
Погодите, как так четыре, когда три? Например, у буквы из верхней строки соседи слева, справа и снизу.

 Профиль  
                  
 
 Re: Число последовательных выборок из 2-мерного массивв
Сообщение22.04.2018, 08:07 


07/08/14
2910
arseniiv в сообщении #1306269 писал(а):
Погодите, как так четыре, когда три? Например, у буквы из верхней строки соседи слева, справа и снизу.

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

 Профиль  
                  
 
 Re: Число последовательных выборок из 2-мерного массивв
Сообщение22.04.2018, 15:37 
Заслуженный участник
Аватара пользователя


27/04/09
24309
Уфа
В общем, я так понимаю, у вас всё же некоторые значения, индексированные двумя числами: $$\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$ берутся его начальные отрезки.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: oleg_2019


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group