Grigoriy wrote: как-будто в выкладках сферху будет дыра, Григорий: лишь сумма модулей (поскольку может А(i)-i < 0) |А(0) - 0| + |А(1) - 1| + |А(2) - 2| + ... + |А(11) -11| будет (модули упорядочены) 0 + 1 + 2 + ... + 11 = 66 при поворотах по часовой стрелке, но сравнение с суммой (А(0) - 0) + (А(1) - 1) + (А(2) - 2) + ... + (А(11) -11) = 0 НЕ будет приводить к противоречию и значит выводов нельзя выводить.

различные А(i)-i ограничивают посадки гостей (один из них должен сесть на своё место), что видимо противорчит возможности произвольной посадки, но пока не нашёл убедительного и ясного рассуждения

Всё в порядке, дорогой друг Хайдук, всё под контролем. Никаких дыр.

ну-ну

Вы невнимательно изучили творчество гениального Теэтета, дорогой друг. Но это неважно. Как учит нас не менее гениальный Руми

Благословенна глупость, коль она на благо от Аллаха мне дана.

Так что Ваше впутывание ни к селу ни к городу модулей - безусловно послано Аллахом Вам на благо.

ни гениального Теэтета, ни такового Руми не знаю

Я думаю, что Вам ещё не поздно расширить Ваше образование, изучив творчество сих великих гениев. Но нужно ли?! Повторяю:

Благословенна глупость, коль она на благо от Аллаха мне дана.

Всё-таки поясню. Если А(i) меньше i, то надо не брать модуль, а прибавить 12 - и тогда получится число, показывающее на сколько надо повернуть стол чтобы i-ый товарищ оказался на своём месте. По модулю 12 это тоже самое число.

ну, как правило глупость меня чурается как оборотень деревянного креста

дело в том, Григорий, что разница А(i)-i < 0 означает поворот в другую сторону, ПРОТИВ часовой стрелки; такие -разницы могут (в зависимости от того как пьяные гости обрушились на стулья) обнулить равные им +разницы (для других i) ПО стрелке и останется отличная от 0 разница +/-6 лишь благодаря тому, что число 11 нечётное; трюк не пройдёт, однако, с нечётным числом гостей

Хайдук, мне конечно лень искать, что и как Григорий писал, но по сути речи о взятии модуля (абсолютной величины) не могло идти. Речь шла о вычислениях по модулю 12. Используется то же слово, но смысл у него другой.

это я понимаю, +/- разницы это по модулю 12

Извините, не вчитался. Думал Вы по-прежнему Григория опровергаете.
Для нечетных n эта сумма (n+1)n/2 = 0 (mod n), и приведенное решение не работает. Более того реально существует перестановка, исключающая больше одного совпадения при любом повороте стола.

Хайдук wrote: Разумеется. Но разве я утверждал что-то для нечётных n?

При частом сравнении сложных объектов полезной оказывается идея хеширования, сокращающая время перебора и состоящая в том, что на множестве этих объектов вводится некоторая функция и сравниваются не они, а значения этой хеш-функции; к самим же объектам обращаются только при совпадении ее значений на них, хранимых в их классах хеш-эквивалентности в виде хеш-таблицы. Эти хеш-значения должны просто вычисляться и пореже (по возможности равномерно) совпадать.

Чем больше область значений применяемой хеш-функции, тем меньше ожидаются их совпадения. Например, если объектами являются подмножества пронумерованного множества, то в качестве хеш-функции можно взять мощность этих подмножеств. Так я и сделал и решил некую задачу на компьютере за 2 часа; а потом просто сменил хеш-функцию, взяв вместо мощности подмножества сумму исходных номеров его элементов, гораздо более многозначную, и решил ту же самую задачу всего за 2 минуты! Кстати, номера элементов тоже, по сути, есть хеш-значения, реноме элементов.

P.S. А если бы я хеш-функцию не использовал, то не решил бы задачу за разумное время вообще.

сам-пят wrote: Оптимистичное заявление...
сам-пят wrote: Это просто очень частный случай.

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

Vladimirovich wrote:
Я заявил это конкретно, по факту. Исходное множество у меня состоит из 255 элементов, пронумерованных от 0 до 254. Мощность рассматриваемых мною его подмножеств в упомянутой задаче не превосходит 69, всего-то. А вот если складывать номера элементов подмножества, то сумма может достигать, правда, не 186 + ... + 254, но 10 351, что тоже гораздо больше 69.

сам-пят wrote: Это самое последнее из критериев, которые нужно использовать при выборе хэш-функции

Vladimirovich wrote:
Не совсем понял, поскольку и до этого-то я додумался не сразу.

сам-пят wrote:
Главный критерий хэш-функции это вероятность коллизий. А для криптографии еще и стойкость к обратному преобразованию, но это тут лишнее, как я понимаю.
Поэтому число возможных вариантов должно быть как можно больше. Для бытовухи достаточно 32 (2 лярда) или 64 (очень очень много) битного числа в качестве хэша даже для очень больших массивов.

При сложении как выше вариантов маловато, притом коллизии возникают при самом простом 1+4 и 2+3. Это неэффективно
Вообще обычно уже есть готовые классы для этого типа HashMap, так что изобретать велосипед не нужно, там уже все встроено

Если же хочется немного своё, то тут обзорчик Некриптографические хеш-функции
Можно взять старинную CRC32, на ней все архиваторы древние целостность архивов проверяли
habr.com/post/178955/

Vladimirovich wrote:
Вряд ли стоит говорить о неэффективности, когда задача оказывается решенной за 2 минуты (вместо 2 часов). Объекты у меня - это множества, набираемые из последовательности чисел 0, ..., 254 по некоторому критерию, каждый раз разному. Заранее их нет. И задача состоит в том, чтобы подсчитать количество различных множеств, поскольку они могут совпадать. Какую "более эффективную" хеш-функцию здесь можно предложить? Я использовал уже встроенную просто функцию Sum().

сам-пят wrote: Ну и ладушки

Vladimirovich wrote:
Я, между прочим, пробовал использовать хеш-коды, вырабатываемые по умолчанию для моих множеств (списков), какие-то довольно большие числа. Тут же возникли проблемы с памятью. Может, я не понимаю, что такое хеш-таблица, но я брал ее размером с максимальное хеш-значение.

сам-пят wrote: Ну при таком подходе ни один компьютер не потянул бы современные 512 битные хэш-ключи (например SHA-512)

Я почему возник здесь с идей хеш-функции. Просто мне захотелось изложить эту полезную идею просто и кратко, для чайников. А то даже в Википедии все это излагается каким-то нечеловеческим языком. ((

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

Совсем простенькая задачка.


Расположить 6 неотточенных круглых карандашей что бы все они касались друг друга.

Grigoriy wrote:

Всё гораздо проще:



Я очень озлился на себя - увидев эту картинку - что м б проще - а я не додумался

У меня красивее

В общем так