Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5] 6 7 8 9   вперед  Ctrl      все
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13553
Gennadiy Usov
Dima T
пропущено...
Как понимаю "лесенка" - это вхождение в размер К всех размеров менее К.
Если так, то в любой системе счисления есть "лесенка", т.к. они все позиционные.
Не совсем так.

В сообщении21689842хорошо видны эти "лесенки".
Если идти сверху картинки К=5, то видно, что:
- сначала "лесенка" 5х5 - 5 сочетаний
- далее для 1 "лесенка" 4х4 - 4 сочетания
- далее для 01 "лесенка" 3х3 - 3 сочетания
- далее для 11 "лесенка" 3х3 - 3 сочетания. Итого 15 сочетаний.
А слева в каждом из этих сочетаний сформированы числа от 00 до 11.(К-3 = 2)

Слабо понял о чем речь. Меня другой вопрос интересует: в чем польза от этой красоты? Как это связано с расстановкой ферзей?
30 сен 18, 15:03    [21690392]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 39863
Gennadiy Usov
Имеется несколько последовательностей чисел: 1,2,3, далее 1,2,3,4,5,6, далее 1,2,3,4,5,6,7,8,9, и т.д.
Для каждой нужно найти все сочетания. При этом:
В первой последовательности в одном сочетании не могут быть 1 и 2, во второй - 1 и 3, 2 и 4, 3 и 5, 4 и 6,
в третьей - 1 и 4, 2 и 5, 3 и 6, 4 и 7, 5 и 8, 6 и 9 и т.д.
Здесь видно, что существует некоторая прогрессия, которую можно распространить на последовательность, длиной 3 х К.
Вот и все.

Давайте опишем задачу в форате контестера.

Test1

Input:
Numbers:1,2,3
Exclude:1,2


Output:
Empty


Test2

Input:
Numbers:1,2,3,4,5,6
Exclude:1,2;2,4;3,5;4,6


Output:
Empty


Верно?
30 сен 18, 15:07    [21690394]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
Dima T
Слабо понял о чем речь. Меня другой вопрос интересует: в чем польза от этой красоты? Как это связано с расстановкой ферзей?
Процедура21689747, которая определяет сочетания "один из пары", уже включена в один из алгоритмов21690219.

А красота в том, что в одном сочетании включены элементы двух других сочетаний. Жалко, что Вы не поняли.
30 сен 18, 18:48    [21690483]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
Должно быть так:
Test1
Input:
Numbers:1,2,3
Exclude:1,2;2,3

На самом деле, легко проглядывается зависимость второй строчки от первой строчки в виде формулы.
Пока я эту формулу ещё не вывел.
30 сен 18, 18:52    [21690484]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 39863
Gennadiy Usov,

А вывод какой?
30 сен 18, 18:57    [21690489]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
Dima T
Схематично вывод делается так
function print_bit(value) {
  mask = 1 << K;
  while(mask != 0) {
     if((value & mask) == 0) {
         print("0");
     } else {
         print("1");
     }
     mask = mask >> 1;
}
Если я правильно понял, value & mask определяет значение (0 или 1) бита, определенного маской? А mask - позиция бита - 1, остальные 0?

А while(mask != 0) означает, что сдвиг маски будет больше К (1 выйдет за границу К)?
30 сен 18, 19:07    [21690495]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
mayton
Gennadiy Usov,
А вывод какой?
Просто в одном из алгоритмов можно переставлять 3 (6, 9, ...., в зависимости от размера доски) вертикалей. Но если эти вертикали переставлять одновременно (те же сочетания), то появляется несовместимость некоторых вертикалей на одновременную перестановку.
30 сен 18, 19:12    [21690501]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13553
Gennadiy Usov
Dima T
Слабо понял о чем речь. Меня другой вопрос интересует: в чем польза от этой красоты? Как это связано с расстановкой ферзей?
Процедура21689747, которая определяет сочетания "один из пары", уже включена в один из алгоритмов21690219.

А красота в том, что в одном сочетании включены элементы двух других сочетаний. Жалко, что Вы не поняли.

Алгоритм где-нибудь простыми словами описан? Заниматься реверс-инженерингом непонятного кода нет ни какого желания.

+ PS напомнило анекдот
Всплывает на дальнем востоке подводная лодка, американская.
На берегу сидит чукча.
Капитан подлодки спрашивает: - Как проплыть к Берингову проливу, а то у
нас приборы сломались?
Чукча отвечает: - Курс Зюйд-Зюйд-Вест.
Tanks, сказал капитан подлодки, и она погрузилась в море.
Через один час всплывает Русская подлодка.
Русский (Р) Капитан подлодки спрашивает чукчу (Ч):.
Р. - Ты не видел тут американскую подлодку?
Ч. Видел.
Р. Куда она поплыла?
Ч. Курс Зюйд-Зюйд-Вест.
Р. Ты не умничай, пальцем покажи.
30 сен 18, 19:39    [21690512]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13553
Gennadiy Usov
Dima T
Схематично вывод делается так
function print_bit(value) {
  mask = 1 << K;
  while(mask != 0) {
     if((value & mask) == 0) {
         print("0");
     } else {
         print("1");
     }
     mask = mask >> 1;
}
Если я правильно понял, value & mask определяет значение (0 или 1) бита, определенного маской? А mask - позиция бита - 1, остальные 0?

А while(mask != 0) означает, что сдвиг маски будет больше К (1 выйдет за границу К)?

mask это 1 и К ноликов. После каждого сдвига на один нолик меньше. В итоге 1 уйдет и mask == 0
value & mask дает либо ноль либо mask если в этом разряде у value стоит 1.
30 сен 18, 19:42    [21690515]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
Dima T
Алгоритм где-нибудь простыми словами описан? Заниматься реверс-инженерингом непонятного кода нет ни какого желания.
Так Вы уже его читали. 21690386плюс картинка21689842

Так что не понятно?
30 сен 18, 19:52    [21690520]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 39863
Gennadiy Usov
mayton
Gennadiy Usov,
А вывод какой?
Просто в одном из алгоритмов можно переставлять 3 (6, 9, ...., в зависимости от размера доски) вертикалей. Но если эти вертикали переставлять одновременно (те же сочетания), то появляется несовместимость некоторых вертикалей на одновременную перестановку.

Я вообще не это спрашивал.

Если на вход этой волшебной функции подать цифры и ограничители которые я привёл.

То что функция должна выдать на выход.
30 сен 18, 19:55    [21690521]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
mayton
Я вообще не это спрашивал.
Если на вход этой волшебной функции подать цифры и ограничители которые я привёл.
То что функция должна выдать на выход.
Если на входе 3(6,9,...) цифр и есть ограничения, то на выходе должны быть сочетания этих цифр, которые не противоречат ограничениям.
30 сен 18, 20:02    [21690524]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
Dima T
Gennadiy Usov
Здесь необходимо уточнение (или сравнение), так как пока путаюсь:
- какое максимальное целое число в битах можно представить в компьютере;
- какой максимальный размер массива Р можно представить в компьютере?
Хочется сравнить эти числа, так как в дальнейшем идет разговор о больших досках (соседний топик).
Любое число. Процессор оперирует 32 и 64 битными словами, но никто не мешает взять массив слов и логически рассматривать его как одно число. Операции сравнения (больше, меньше, равно) сделать элементарно для этого числа.
Максимальный размер массива зависит от количества имеющейся памяти и размера элемента массива. Для простоты считай что возможен массив из 100 млн. элементов.

В принципе без разницы как представлено число: массив слов (двоичное представление) или просто массив где один элемент один бит. Второй способ просто займет больше памяти и медленнее будет обратываться.
Хорошо.

Пример: доска 997х997, 249 квадратов ферзей. Как представить сочетания из 249 объектов? В битах, в массиве слов и т.д.
30 сен 18, 20:06    [21690525]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13553
Gennadiy Usov
Хорошо.

Пример: доска 997х997, 249 квадратов ферзей. Как представить сочетания из 249 объектов? В битах, в массиве слов и т.д.

Ничего хорошего. Я не понимаю почему 249 а не 997? В задаче на доску N*N надо выставить N ферзей.
Непонятно на основании чего сделано упрощение. С другой стороны если упрощено до каких-то "квадратов ферзей", то это уже отдельная фигура со своим поведением.
В общем я догадываюсь что выведены какие-то дополнительные правила, но эти правила нигде не озвучены. Про них и спрашиваю.
30 сен 18, 20:19    [21690536]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
Dima T
Gennadiy Usov
Хорошо.
Пример: доска 997х997, 249 квадратов ферзей. Как представить сочетания из 249 объектов? В битах, в массиве слов и т.д.
Ничего хорошего. Я не понимаю почему 249 а не 997? В задаче на доску N*N надо выставить N ферзей.
Непонятно на основании чего сделано упрощение. С другой стороны если упрощено до каких-то "квадратов ферзей", то это уже отдельная фигура со своим поведением.
В общем я догадываюсь что выведены какие-то дополнительные правила, но эти правила нигде не озвучены. Про них и спрашиваю.
Здесь ещё больше объяснять.
Процедура, которая определяет квадраты ферзей, 21690219.
Но мы говорим не о ферзях, а о сочетаниях объектов. Объектов 249. Как быть с представлением сочетаний?
30 сен 18, 20:24    [21690542]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 39863
Gennadiy Usov
mayton
Я вообще не это спрашивал.
Если на вход этой волшебной функции подать цифры и ограничители которые я привёл.
То что функция должна выдать на выход.
Если на входе 3(6,9,...) цифр и есть ограничения, то на выходе должны быть сочетания этих цифр, которые не противоречат ограничениям.

Я хотел узнать конкретное число(числа) для 123
30 сен 18, 20:37    [21690550]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
mayton
Gennadiy Usov
пропущено...
Если на входе 3(6,9,...) цифр и есть ограничения, то на выходе должны быть сочетания этих цифр, которые не противоречат ограничениям.

Я хотел узнать конкретное число(числа) для 123
100, 010, 001, 101
30 сен 18, 20:52    [21690561]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 39863
Gennadiy Usov
mayton
пропущено...

Я хотел узнать конкретное число(числа) для 123
100, 010, 001, 101

Аха...

Тоесть будет так:

Input:
Numbers:1,2,3
Exclude:1,2;2,3

Output:
1,
2,
3,
13


Верно?
30 сен 18, 21:41    [21690584]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 39863
Хм.. мне вот не нравится ограничение в исключение пар. А если надо будет исключать тройки? Четверки?
1 окт 18, 01:07    [21690657]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 39863
Как-то так.

object Main {

  def parseArgNumbers(argNumbers: String): List[Int] = argNumbers.split(",").map(s => s.toInt).toList

  def parseTuple(s : String) : (Int,Int) = {
    val sp = s.indexOf(",")
    (s.substring(0, sp).toInt, s.substring(sp + 1).toInt)
  }

  def parseExclude(argExclude: String): List[(Int,Int)] = argExclude.split(";").map(s => parseTuple(s)).toList

  def containsTuple(subNumbers: List[Int], pair: (Int, Int)): Boolean = {
    subNumbers.contains(pair._1) && subNumbers.contains(pair._2)
  }

  def contains(subNumbers: List[Int], excluded: List[(Int, Int)]): Boolean = {
    //for(pair <- excluded) {
    //  if (containsTuple(subNumbers,pair)) return true
    //}
    //false
    // TODO: I hope, breaking after 1st element of lazy collection will make perfomance
    return excluded.filter(pair => containsTuple(subNumbers,pair)).take(1).size == 1
  }

  def trickyCombinations(numbers: List[Int], excludes: List[(Int, Int)]): Unit = {
    val size = numbers.size
    for(i <- 1 to size) {
      printf(s"The combinations $i of $size\n")
      numbers.combinations(i).foreach(f => {
        if (!contains(f,excludes)) {
          for (v <- f) printf("%s,", v)
          printf("\n")
        }
      })
      printf("\n\n")
    }

  }

  def main(args : Array[String]) : Unit = {

    printf("\nNumbers : ")
    val argNumbers = "1,2,3,4,5" //scala.io.StdIn.readLine()

    printf("\nExclude : ")
    val argExclude = "1,2;2,3"   //scala.io.StdIn.readLine()

    println()

    val numbers = parseArgNumbers(argNumbers)
    val excludes = parseExclude(argExclude)

    trickyCombinations(numbers,excludes)

  }

}
1 окт 18, 01:41    [21690660]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 39863
Output
+
The combinations 1 of 5
1,
2,
3,
4,
5,


The combinations 2 of 5
1,3,
1,4,
1,5,
2,4,
2,5,
3,4,
3,5,
4,5,


The combinations 3 of 5
1,3,4,
1,3,5,
1,4,5,
2,4,5,
3,4,5,


The combinations 4 of 5
1,3,4,5,


The combinations 5 of 5
1 окт 18, 01:42    [21690661]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
mayton
Хм.. мне вот не нравится ограничение в исключение пар. А если надо будет исключать тройки? Четверки?
В сообщении я попробовал составлять сочетания (второго уровня) из двух сочетаний (первого уровня). В данном случае одно из сочетаний первого уровня - "линейка". А Dima T меня не понял.

Ранее я рассматривал задачу 123, 123456, и т.д. 2130207621482003. Попробую ещё раз объяснить мой метод решения этой задачи.
В данной задаче интересно рассмотреть задачу объединения в одном сочетании 3-х сочетаний. Рассмотрим.
Все объекты, которые участвуют в данной задаче, кратны 3: 3,6,9,12,….
Следовательно, в каждом случае можно разделить конкретную задачу на 3 участка:
-для 3-х объектов: 1, 2, 3
-для 6-и объектов; 12, 34, 56
- для 9-и объектов: 123, 456, 789. и т.д.
Можно выбирать сочетания для 1-го и 3-го участка и составлять объединенное сочетание (средний участок пока нули).
Если теперь добавлять средний участок, то сравниваются на наличие 1 одинаковые колонки по номеру в 3-х участках. Если совпадают, то данное сочетание из среднего участка пропускается.
Пока так на пальцах.
1 окт 18, 07:17    [21690701]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 39863
Gennadiy Usov
mayton
Хм.. мне вот не нравится ограничение в исключение пар. А если надо будет исключать тройки? Четверки?
В сообщении я попробовал составлять сочетания (второго уровня) из двух сочетаний (первого уровня). В данном случае одно из сочетаний первого уровня - "линейка". А Dima T меня не понял.

Я не понимаю что такое "уровни". Объясни. Ты не забывай что здесь - айтишники. Не математики.
Нам сложно искать смыслы в художественных словах и эпитетах.

Лучший вариант донести алгоритм - это привести код который всем понятен. И подкрепить
примером в формате Input/Output как я писал выше.
1 окт 18, 10:21    [21690799]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 39863
Gennadiy Usov
Dima T
пропущено...
Почему?
Здесь необходимо уточнение (или сравнение), так как пока путаюсь:
- какое максимальное целое число в битах можно представить в компьютере;

Возможно отвечали. Я просто добавлю.

Не надо ставить так вопрос.

Любое число можно представить на которое хватит памяти. Но это не означает
что вы с этим мега-числом сможете эффективно работать.

Программирование - это постоянная инженерия возможностей
- CPU (регистры)/Memory
- Язык и компиллятор и типы данных
- Библиотеки

Мы всегда ищем компромиссы. Как бы сделать задачу. На базовых регистрах CPU (32/64).
На расширенных. На языковых типах данных. На библиотеках.

Поэтому не бывает такого вопроса. От задачи надо идти.
1 окт 18, 10:36    [21690807]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 39863
Gennadiy Usov
- какой максимальный размер массива Р можно представить в компьютере?

Хочется сравнить эти числа, так как в дальнейшем идет разговор о больших досках (соседний топик).

Уже почти ответил выше. Практически размер массива будет ограничен вашей памятью ПК.
Можно и больше. Но в этом случае мы задействуем диск со всеми вытекающими.

Сравнение двух сверх-больших чисел - это задача класса линейной вычислительной сложности. Тоесть чем длиннее числа
тем медленнее они будут сравниваться.
1 окт 18, 10:40    [21690811]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5] 6 7 8 9   вперед  Ctrl      все
Все форумы / Программирование Ответить