2014 dxdy logo

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

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


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


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



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


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

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


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

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

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


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

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

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


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

-- 19.04.2018, 06:42 --

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

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


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

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


12/08/14
287
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
22322
Уфа
upgrade в сообщении #1305353 писал(а):
для "двумерного" ряда элементов
$a,b,c,d,e,f,g,...z$
$\alpha,\beta,\gamma,\delta,\varepsilon,\zeta,\eta,...\omega$
И где же тут двумерность?

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

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

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



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

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


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

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