Здравствуйте, PC_2, Вы писали:

PC_>Здравствуйте, samius, Вы писали:

PC_>>>Вообщето скип, это почти тот же фильтр результата.
S>>Ты даже не понял, что результаты по скипу не вычисляются? Ты походу слил, но сам еще не понял это.

PC_>Скипать результаты не проблема в РС.

PC_>Но ты как единственный любитель преждевременных оптимизаций тут должен был уже понять,
PC_>что программе на Си, например, было бы абсолютно по барабану начинать свои счетчики
PC_>с 10 со 100 тыс или с 1 миллиарда. Чего не скажешь о твоем "прогрессивном" решении
PC_>со скипом, которые по твоей алгоритмической сложности эквивалент РС.

PC_>Что не скажешь о твоем решении.
Размещение от перестановки отличаешь?
Умататся

Ну что, покзывай свой алгоритм которому по барабану с чего начинать, но напомню, речь об размещениях. Сложность твоей реализации, которую ты мне покажешь, должна быть O(C). Успехов

Здравствуйте, samius, Вы писали:

S>Я думал что ты записал решение общего случая, а оказалось что 3 из n. Да, может и во внешних. Но продолжишь ли ты его по индукции до k из n?

Слушай, ты вообще, в целом, синтаксис RS понимаешь? Или PC_2 тебя таки запутал в конец?

S>Пока нет оснований полагать что будет такая оптимизация. Если и будет, чего она будет стоить?
Да ничего она не будет стоить, скорее всего.

Она, скорее всего, получится сама собой.
Ну и потом что же можно интерпретировать оптимально, а что нет -- вопрос и правда отдельный.
Во всяком случае переборщики такого вида, совершенно очевидно можно интерпретировать эффективно. Я знаю, как это сделать. Я даже больше скажу, я не уверен, что общий случай получится реализовать как-то ещё, кроме как эффективно

Понимаешь, вот, например, если у тебя будет рекурсивная функция, которая генерит переборщик размещений без повторов, то она будет какой-то такой примерно:

foo( X, 1 ) { return X }
foo( X, count )
{
   !Y = переборщик, связанный с X, таким образом, что перебирает все те же значения, что и X, кроме того значения, в котором сейчас находится Х
   return переборщик декартова произведения их X и результата foo( Y, count - 1 )   
}

E>>C -- переборщик букв.
E>>(C!=D?D) -- связанный с C переборщик, который перебирает для какой-то позиции С все буквы, кроме той, которая выбрана в С
S>N^2
Нет, сам по себе (C!=D?D) это N-1 позиция.
Соответственно декартово произведение C и (C!=D?D) -- это N* (N-1)

E>>(E!=C && E!=D ?E) -- связанный с С и D переборщик, который для каждой позиции С и D перебирает все буквы, кроме тех, котрые выбраны С и D...
S>N^3
N(N-1)(N-2)


E>>C+(C!=D?D)+(E!=C && E!=D ?E) -- переборщик конкатенаций этих троек букв...
S>Круто. Запишешь для четверок и пятерок?
1) запишу. Я думаю, что ты тоже запишешь.
2) Для общего случая N не запишу. Надо полумать, как выражать понятие "связанный переборщик" или "зависимый" или "согласованный", например.
3) Для сведения: при фиксированном K и N->oo, O( N*(N-1)*(N-2)*(N-3)*...*(N-K) ) = O( N^(K+1) )

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, samius, Вы писали:

S>>Я думал что ты записал решение общего случая, а оказалось что 3 из n. Да, может и во внешних. Но продолжишь ли ты его по индукции до k из n?

E>Ну тут есть вопрос, как это сделать понятно и удобно для интерпретации.
Нет, не только в этом.

S>>Круто. Запишешь для четверок и пятерок?

E>А в чём проблема:
E>Вот для чётвёрок, например:

E>C+(C!=D?D)+(E!=C && E!=D ?E)+(F!=C && F!=D && F!= E ?F)

E>Струтктура выражения, как раз легко обощается на сколько хочешь букв.
И ты споришь с тем что это переборное решение? Я прямо вижу череду for-ов, каждый из которых пробегает весь диапазон 0..N-1 и в каждом проверки.
c!=d в первом — но ты не исключаешь символ c из рассмотрения. С ним надо сравнивать каждый счетчик.
Это полнопереборное решение, но фильтрация не в конце, а в между делом.

E>Проблема тут совсем другого рода. Как удобно и понятно выражать факт связанности каких-о переборщиков в разных частях выражения. Ну типа, что вот это-вот -- это текущая позиция вон-того-вот переборщика из той части...
обычно это делается копированием состояний переборщиков, построением переборщиков верхнего уровня, и т.п. Если посмотришь на мое решение — увидишь что переборщики (k) рекурсивно ссылаются на переборщики (k-1)

Здравствуйте, samius, Вы писали:

E>>э-э-э, "вернуть" внутри "для каждого" концептуально ен ясны для меня...
S>Это же переборщик. Но он перебирает не числа а решения.

Я так понимаю, что "для каждого" -- это цикл. то есть у нас из функции возвращается сразу много значений параллельно? Или что это всё обозначает?

S>Да, теперь вижу что не последующая. Но разница в кол-ве вычислений все равно гигантская.
попробуй её оценить

S>Можно ли записать это решение для любого числа буков?\
Ты понимаешь, что я пишу? Я могу, в принципе, подробнее писать.
Вот, как, например, я выражение для троек по кусочкам разобрал...

Здравствуйте, samius, Вы писали:

S>Позиция такого переборщика — это срез по всем счетчикам, сколько бы их не было, со всеми состояниями массивов. Ты говоришь о 'хибернейте' интерпретатора, видимо.

1) Это всего лишь спор о терминах
2) Вообще-то, это сильно зависит от реализации интерпретатора.

Здравствуйте, samius, Вы писали:

S>Ну что, покзывай свой алгоритм которому по барабану с чего начинать, но напомню, речь об размещениях.

Сначала обьясни свое решение. Что такое синт. конструкция SKIP ? Это встроеная грушка ?
Так давай я тоже встрою. Правда я думаю если я такое встрою то у меня будет работать по Сишному и начинать
перебор с середины списка.

S>Сложность твоей реализации, которую ты мне покажешь, должна быть O(C). Успехов

Так ты понял о чем я тебе написал, или ты продолжаешь настаивать на скипе и восхищаться, что чтобы скипнуть 1 млн вариантов твоему алгоритму нужно
всего лишь 20 секунд, наверное как и фильтру, когда реальной программе на Си на это нужно примерно 0 секунд ?

Здравствуйте, samius, Вы писали:

S>Это правда для той записи что ты показывал. Каждое отсечение — это if, который нужно вычислить. В твоей записи отсечения небесплатны.
1) число этих if,ов -- o( числа размещений)
2) Опять же, зависит от реализации фильтрации
Ты правда думаешь, что программисты ещё не придумали как работать с разреженными или аналитически описываемыми множествами? многие из проблем, которые тебя пугают носят чисто технический характер и вообще уже давно очень решены.


E>>Сложность будет O(число размещений)...
S>А в моей как раз так и отсекается.
В RS будет так же. Просто посчитай ассмптотику.

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, samius, Вы писали:

E>Слушай, ты вообще, в целом, синтаксис RS понимаешь? Или PC_2 тебя таки запутал в конец?
В общих чертах иногда догадываюсь. Не запутал, замучил.

S>>Пока нет оснований полагать что будет такая оптимизация. Если и будет, чего она будет стоить?
E>Да ничего она не будет стоить, скорее всего.
Ты хочешь исключать из значений переборщиков пройденные символы?

E>Она, скорее всего, получится сама собой.
Есть шутка про то что само собой делается, но не буду.
E>Ну и потом что же можно интерпретировать оптимально, а что нет -- вопрос и правда отдельный.
E>Во всяком случае переборщики такого вида, совершенно очевидно можно интерпретировать эффективно. Я знаю, как это сделать. Я даже больше скажу, я не уверен, что общий случай получится реализовать как-то ещё, кроме как эффективно
Ух ты

E>Понимаешь, вот, например, если у тебя будет рекурсивная функция, которая генерит переборщик размещений без повторов, то она будет какой-то такой примерно:

foo( X, 1 ) { return X }
E>foo( X, count )
E>{
E>   !Y = переборщик, связанный с X, таким образом, что перебирает все те же значения, что и X, кроме того значения, в котором сейчас находится Х
E>   return переборщик декартова произведения их X и результата foo( Y, count - 1 )   
E>}
E>

E>>>C -- переборщик букв.
E>>>(C!=D?D) -- связанный с C переборщик, который перебирает для какой-то позиции С все буквы, кроме той, которая выбрана в С
S>>N^2
E>Нет, сам по себе (C!=D?D) это N-1 позиция.
E>Соответственно декартово произведение C и (C!=D?D) -- это N* (N-1)
Кажись понял. Ты хочешь сгенерировать переборщик по выражению?

E>>>(E!=C && E!=D ?E) -- связанный с С и D переборщик, который для каждой позиции С и D перебирает все буквы, кроме тех, котрые выбраны С и D...
S>>N^3
E>N(N-1)(N-2)
Понял. Но что-то мне не нравится, пока не пойму что

E>>>C+(C!=D?D)+(E!=C && E!=D ?E) -- переборщик конкатенаций этих троек букв...
S>>Круто. Запишешь для четверок и пятерок?
E>1) запишу. Я думаю, что ты тоже запишешь.
E>2) Для общего случая N не запишу. Надо полумать, как выражать понятие "связанный переборщик" или "зависимый" или "согласованный", например.
E>3) Для сведения: при фиксированном K и N->oo, O( N*(N-1)*(N-2)*(N-3)*...*(N-K) ) = O( N^(K+1) )
Принято

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, samius, Вы писали:

S>>Это правда для той записи что ты показывал. Каждое отсечение — это if, который нужно вычислить. В твоей записи отсечения небесплатны.
E>1) число этих if,ов -- o( числа размещений)

Егор, было уже, сделать \~ конструкцию. Возвращает тру если все элементы уникальны и противном случае фолс.
В принципе когда будут функции, туже задачу можно сделать оформив однострочную функцию с двумя циклами.

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, samius, Вы писали:

E>>>э-э-э, "вернуть" внутри "для каждого" концептуально ен ясны для меня...
S>>Это же переборщик. Но он перебирает не числа а решения.

E>Я так понимаю, что "для каждого" -- это цикл. то есть у нас из функции возвращается сразу много значений параллельно? Или что это всё обозначает?
Это автомат, который возвращает значения при каждом обращении и переводит себя в очередное состояние.

S>>Да, теперь вижу что не последующая. Но разница в кол-ве вычислений все равно гигантская.
E>попробуй её оценить

S>>Можно ли записать это решение для любого числа буков?\
E>Ты понимаешь, что я пишу? Я могу, в принципе, подробнее писать.
E>Вот, как, например, я выражение для троек по кусочкам разобрал...
Отбой. Можно. А можно коротко и удобно, и что бы длина записи не зависела от k?

Здравствуйте, samius, Вы писали:

E>>Ну тут есть вопрос, как это сделать понятно и удобно для интерпретации.
S>Нет, не только в этом.
А в чём ещё?

S>И ты споришь с тем что это переборное решение? Я прямо вижу череду for-ов, каждый из которых пробегает весь диапазон 0..N-1 и в каждом проверки.
Ну и зря ты это видишь. попробуй подумать, КАК ЭТО РЕАЛИЗОВАТЬ ЭФФЕКТИВНО?
S>c!=d в первом — но ты не исключаешь символ c из рассмотрения. С ним надо сравнивать каждый счетчик.
Почему? Это всего лишь операция полиморфного переборщика в реализации будет. "наложить фильтр"...
S>Это полнопереборное решение, но фильтрация не в конце, а в между делом.\
Ну и что? Это всего лишь вопрос, как эффективно реализовать итерацию так заданного множества. И только. Для разных сред итерация будет эффективная разная, кстати. И что?

E>>Проблема тут совсем другого рода. Как удобно и понятно выражать факт связанности каких-о переборщиков в разных частях выражения. Ну типа, что вот это-вот -- это текущая позиция вон-того-вот переборщика из той части...
S>обычно это делается копированием состояний переборщиков, построением переборщиков верхнего уровня, и т.п.
Что значит "копирование состояний переборщиков"? Мы же обсуждаем язык, ан котором можно ПРОДЕКЛАРИРОВАТЬ МНОЖЕСТВО перебираемых состояний. "Копировать" -- это слово с процедурного уровня. То есть особенность реализации интерпретатора, а вовсе и не особенность семантики языка. Оно не должно присутствовать на уровне конструкция языка.

Если посмотришь на мое решение — увидишь что переборщики (k) рекурсивно ссылаются на переборщики (k-1)
Которое из? То, где стоит возврат в цикле? Я не понимаю его записи. Объясни как-то другими словами.
В частности, я задал простой вопрос. Там стоит возврат в цикле. Это что значит? Возврат первого попавшегося значения, или что-то ещё?

Здравствуйте, PC_2, Вы писали:

PC_>Здравствуйте, samius, Вы писали:

S>>Ну что, покзывай свой алгоритм которому по барабану с чего начинать, но напомню, речь об размещениях.

PC_>Сначала обьясни свое решение. Что такое синт. конструкция SKIP ? Это встроеная грушка ?
Это метод, который пропускает указанное кол-во элементов. Навесной, в ядро языка не входит.

PC_>Так давай я тоже встрою. Правда я думаю если я такое встрою то у меня будет работать по Сишному и начинать
PC_>перебор с середины списка.
Она не встроенная. Да и думаешь ты походу мимо.

S>>Сложность твоей реализации, которую ты мне покажешь, должна быть O(C). Успехов

PC_>Так ты понял о чем я тебе написал, или ты продолжаешь настаивать на скипе и восхищаться, что чтобы скипнуть 1 млн вариантов твоему алгоритму нужно
PC_>всего лишь 20 секунд, наверное как и фильтру, когда реальной программе на Си на это нужно примерно 0 секунд ?
Я понял о чем ты написал, но видимо ты не понял, что речь идет о переборе размещений а не перестановок. Для перестановок можно быстро получить i-ую. Для размещений тоже можно, но не мгновенно.
Или потрудись хотя бы ссылку дай на мгновенный алгоритм получения i-ого размещения. Ну не мгновенный, а что бы хотя бы

работать по Сишному и начинать
PC_>перебор с середины списка.

Здравствуйте, samius, Вы писали:

S>В общих чертах иногда догадываюсь. Не запутал, замучил.
+1 Хорошо, значит мы пока понимаем друг друга вилимо. А то меня очень смутило, что на выражение, описывающее тройки букв ты сказал, что думал, что это для общего случая...

S>Ты хочешь исключать из значений переборщиков пройденные символы?
Ну и это тоже. Это правда простой и технический вопрос.

E>>Она, скорее всего, получится сама собой.
Ну у тебя в голове сидит ровно одна архитектура интерпретатора. А она может быть не одна.

S>Ух ты
Да не "ух" и не "ты".

В сё сведётся к тому, что у тебя, например, будут переборщики диапазона, коллекции диапазонов, и просто битсет.
Ну и будет какой-то апдейт этого всего, при изменениях в связанном переборщике.
И ты будешь уметь их внутри интерпретатора сочетать. И каждый раз, когда будешь вычислять новый переборщик, будешь смотреть как его оптимально представить. Так что у тебя само собой получится, что будет K переборщиков, уже профильтрованных, и каждый относительно эффективный. и потом поверх этого будет переборщик их декартова произведения, который будет их просто ++ить и ресетить в нужном порядке. И всё. Это на однонитевой реализации если. Если речь идёт о парралеллелищзме, то самый внешний цикл, например расщепят по ядрам/машинам.
А если о массововм, то наоборот, самый внутренний. И вот в этом вот последнем случае как раз связанные переборщики реализовать не удастся. но там, как раз, будут удобны фильтры в самом вложенном цикле.

Это, как бы, наивная реализация, на самом деле. И в чём проблема? В рассылке апдейтов?

S>Кажись понял. Ты хочешь сгенерировать переборщик по выражению?
Нет, я вообще хочу разделить процедурный и семантический аспекты кода. И PC_2, кстати, тоже. Мы на этом с ним и сошлись. В этом одна из идей RS. Просто он её очень путанно и провокативно излагает.
Суть идеи в том, что в языке С++, например, есть очень много лишних подробностей о том КАК что-то надо сделать. Хотя во многих случаях вполне бы хватило описать только ЧТО мы хотим получить, а КАК мог бы допереть и сам интерпретатор.
Ясно, что универсальный всемогутер так построить трудно. Но вот язык для всяких переборных задачь, вробе бы можно. И дополнить его потом до языка общего назначения -- это, как раз, рутина и проблем не представляет.
проблемы лежат совсем в другой плоскости.

В частности, мне нравится идея PC_2, про то, что множество можно описать сразу несколькими способами, а потом потребовать, чтобы исполнялись все ограничения, например.
но этото тоже потребует как-то выражать, что "это вот" состояние соответствует "тому-вот".
То есть опять попадаем в связанные переборщики...

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, samius, Вы писали:

S>>Это правда для той записи что ты показывал. Каждое отсечение — это if, который нужно вычислить. В твоей записи отсечения небесплатны.
E>1) число этих if,ов -- o( числа размещений)
E>2) Опять же, зависит от реализации фильтрации
E>Ты правда думаешь, что программисты ещё не придумали как работать с разреженными или аналитически описываемыми множествами? многие из проблем, которые тебя пугают носят чисто технический характер и вообще уже давно очень решены.
Э, я же предоставил решение, нет?


E>>>Сложность будет O(число размещений)...
S>>А в моей как раз так и отсекается.
E>В RS будет так же. Просто посчитай ассмптотику.
Да. я понял о чем ты писал. Совпадает.

Но

C+(C!=D?D)+(E!=C && E!=D ?E)+(F!=C && F!=D && F!= E ?F)

на данный момент набор значений всех счетчиков вычисляется лишь раз за выражение.
набор значений C вообще неизменен. Для D уже нужны несколько наборов (для каждого значения из C).
Давай перепишем так

C=('a'..'z')+D=(C|!=C)+E=(D|!=D)+F=(E|!=E)

Здесь виднее что каждый счетчик получается из набора значений предыдущего + некоторое условие на него.

Вобщем то что текущий интерпретатор на такое не способен — это видно, но и невозможности построения соответствующего отрицать не буду.

Здравствуйте, PC_2, Вы писали:

PC_>Егор, было уже, сделать \~ конструкцию. Возвращает тру если все элементы уникальны и противном случае фолс.
PC_>В принципе когда будут функции, туже задачу можно сделать оформив однострочную функцию с двумя циклами.

Ну это всё избыточно, на самм деле.

Выражение же вида C+(D!=C?D)+(E!=C&&E!=D?E)... не проблема сгенерить просто в виде строки, и потом сделать её Eval. Особенно, если вместо C, D, E, F... использовать что-то вроде x1, x2, x3,..
Но хочется без Eval..

Здравствуйте, samius, Вы писали:

S>Это автомат, который возвращает значения при каждом обращении и переводит себя в очередное состояние.
А! Понятно!
Но тогда у тебя описано тоже самое, но в виде автомата, а не в виде перебираемого множества.
те же проверки, что типа "X без х"...

S>Отбой. Можно. А можно коротко и удобно, и что бы длина записи не зависела от k?
Ну вот надо понять, можно ли как-то вменяемо выражать понятие "согласованный переборщик", или, там "подпереборщик". Можно, кстати, потребовать, чтобы граф согласованности переборщиков был лесом, или, хотя бы, ациклическим.

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, samius, Вы писали:

E>>>Ну тут есть вопрос, как это сделать понятно и удобно для интерпретации.
S>>Нет, не только в этом.
E>А в чём ещё?
В сложности алгоритма, тогда я думал. Но пойми, я отвечаю с лагом в несколько сообщений, потому мы в разных точках времени общения находимся. Ну как если бы я был на Марсе. Сейчас я вижу что это вопроса соответствующей интерпретации (для этой задачи) нет.

S>>И ты споришь с тем что это переборное решение? Я прямо вижу череду for-ов, каждый из которых пробегает весь диапазон 0..N-1 и в каждом проверки.
E>Ну и зря ты это видишь. попробуй подумать, КАК ЭТО РЕАЛИЗОВАТЬ ЭФФЕКТИВНО?
Все-все, спокуха! Твоя запись так же эффективна как и то что я приводил при соответствующей интерпретации.

E>>>Проблема тут совсем другого рода. Как удобно и понятно выражать факт связанности каких-о переборщиков в разных частях выражения. Ну типа, что вот это-вот -- это текущая позиция вон-того-вот переборщика из той части...
S>>обычно это делается копированием состояний переборщиков, построением переборщиков верхнего уровня, и т.п.
E>Что значит "копирование состояний переборщиков"? Мы же обсуждаем язык, ан котором можно ПРОДЕКЛАРИРОВАТЬ МНОЖЕСТВО перебираемых состояний. "Копировать" -- это слово с процедурного уровня. То есть особенность реализации интерпретатора, а вовсе и не особенность семантики языка. Оно не должно присутствовать на уровне конструкция языка.
В предыдущем сообщении я заюзал
F=(E|!=E) и это оказалось короче, чем (F!=C && F!=D &&... ? F)
Так что по поводу не должно — можно спорить.

E>Если посмотришь на мое решение — увидишь что переборщики (k) рекурсивно ссылаются на переборщики (k-1)
E>Которое из? То, где стоит возврат в цикле? Я не понимаю его записи. Объясни как-то другими словами.
E>В частности, я задал простой вопрос. Там стоит возврат в цикле. Это что значит? Возврат первого попавшегося значения, или что-то ещё?
Это означает возврат очередного значения и перевод автомата в следующее состояние. Уже объяснял.
Это если взять итератор, попросить его текущее значение и ++ за один вызов. Все это спрятано в этот возврат.

Здравствуйте, samius, Вы писали:

S>Или потрудись хотя бы ссылку дай на мгновенный алгоритм получения i-ого размещения. Ну не мгновенный, а что бы хотя бы
S>

S>работать по Сишному и начинать
PC_>>перебор с середины списка.

А звчем вообще для целей стопа/продолженя уметь нумеровать размещения? Тем более, зачем уметь их нумеровать подряд?

Здравствуйте, samius, Вы писали:

S>Здравствуйте, PC_2, Вы писали:

PC_>>Здравствуйте, samius, Вы писали:

S>>>Ну что, покзывай свой алгоритм которому по барабану с чего начинать, но напомню, речь об размещениях.

PC_>>Сначала обьясни свое решение. Что такое синт. конструкция SKIP ? Это встроеная грушка ?
S>Это метод, который пропускает указанное кол-во элементов. Навесной, в ядро языка не входит.

PC_>>Так давай я тоже встрою. Правда я думаю если я такое встрою то у меня будет работать по Сишному и начинать
PC_>>перебор с середины списка.
S>Она не встроенная. Да и думаешь ты походу мимо.

S>>>Сложность твоей реализации, которую ты мне покажешь, должна быть O(C). Успехов

PC_>>Так ты понял о чем я тебе написал, или ты продолжаешь настаивать на скипе и восхищаться, что чтобы скипнуть 1 млн вариантов твоему алгоритму нужно
PC_>>всего лишь 20 секунд, наверное как и фильтру, когда реальной программе на Си на это нужно примерно 0 секунд ?
S>Я понял о чем ты написал, но видимо ты не понял, что речь идет о переборе размещений а не перестановок. Для перестановок можно быстро получить i-ую. Для размещений тоже можно, но не мгновенно.
S>Или потрудись хотя бы ссылку дай на мгновенный алгоритм получения i-ого размещения. Ну не мгновенный, а что бы хотя бы
S>

S>работать по Сишному и начинать
PC_>>перебор с середины списка.

Сформулируй нормально задачу которую ты решил.
Думается есть разночтение.

Здравствуйте, samius, Вы писали:

S>Вобщем то что текущий интерпретатор на такое не способен — это видно, но и невозможности построения соответствующего отрицать не буду.
S>

Да текущий интерпретатор он того, оптимизацией не занимается ВООБЩЕ. Чего это обсуждать? Это же понятно?
Мало того, это правильно. Так как играться легче с таким интерпертатором...