2014 dxdy logo

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

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


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


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



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


07/08/14
4231
Для натурального ряда длиной $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
17973
Москва
Что Вы понимаете под "последовательными выборками"? Есть выборки с повторениями и выборки без повторений. Есть выборки упорядоченные и выборки неупорядоченные.

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


09/09/14
6328
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
4231
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
12044
Казань
upgrade в сообщении #1305353 писал(а):
дальше для этой выборки не уверен, верно ли выбрать "прямоугольнички"

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

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


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

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


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

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


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

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

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


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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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