294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,037
1

Найти последовательность цифр минимальной длинны, содержащую все N-значные числа

25.01.2016, 20:01. Показов 1315. Ответов 18
Метки нет (Все метки)

Требуется найти минимально возможную последовательность цифр из системы счисления по основанию M, содержащую все N-значные числа включая числа с нулем в начале

так при M=2 и N=2 последовательность 00110 содержит числа 00,01,10,11

Будут ли какие-то идеи кроме наивного поиска есть ли число в последовательности, и если нет то добавить в конец ?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.01.2016, 20:01
Ответы с готовыми решениями:

найти все 4-ёх значные числа, в записи которых нет одинаковых цифр
найти все 4-ёх значные числа, в записи которых нет одинаковых цифр....мне нужно алогритм для Visual...

Найти все n-значные числа, сумма квадратов цифр которых кратна М.
Найти все n-значные числа, сумма квадратов цифр которых кратна М. Помогите, пожалуйста, решить

Найти все n-значные числа, сумма квадратов цифр которых кратна M.
Найти все n-значные числа, сумма квадратов цифр которых кратна M.

Найти все n-значные числа, сумма квадратов цифр которых кратна М
Условие: найти все n-значные числа, сумма квадратов цифр которых кратна М (где n ,M вводится с...

18
90 / 87 / 11
Регистрация: 20.11.2008
Сообщений: 724
26.01.2016, 10:45 2
Интересная задача
Если в этой последовательности не будет повторений, то она должна быть длинны M^N+(N-1)
Если бы такая последовательность всегда существовала, то можно было бы добавлять по символу, следя чтобы в хвосте получалось новое число, а если не получается, возвращаться к предыдущему символу
А если такая минимальная последовательность существует не всегда, то надо ещё подумать
0
Модератор
2959 / 2098 / 450
Регистрация: 26.03.2015
Сообщений: 8,148
26.01.2016, 12:27 3
Цитата Сообщение от wingblack Посмотреть сообщение
есть ли число в последовательности, и если нет то добавить в конец
Этот алгоритм не находит правильный ответ. Результат работы этого алгоритма зависит от того, в каком порядке перебирать числа.
0
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,037
26.01.2016, 12:43  [ТС] 4
Немного обобщу задачу.
Требуется найти текст с как можно меньшей длинной. Не обязательно чтобы это был именно один из текстов с самой минимальной длинной, но нужно постараться найти наиболее короткий.

Добавлено через 5 минут
Цитата Сообщение от ProgJ Посмотреть сообщение
А если такая минимальная последовательность существует не всегда, то надо ещё подумать
Она существует всегда, так как есть самое наивное решение состоящее из всех чисел идущих друг за другом.
Цитата Сообщение от Shamil1 Посмотреть сообщение
Результат работы этого алгоритма зависит от того, в каком порядке перебирать числа.
Согласен, значить можно сделать перебор всех таких вариантов, если скорость вычисления позволяет.
0
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
26.01.2016, 13:04 5
wingblack, это ж гуглится. "shortest common superstring problem". одна из ссылок будет везти на хабр - там простой жадный алгоритм описан.
2
Модератор
2959 / 2098 / 450
Регистрация: 26.03.2015
Сообщений: 8,148
26.01.2016, 14:12 6
Цитата Сообщение от ProgJ Посмотреть сообщение
Если бы такая последовательность всегда существовала, то можно было бы добавлять по символу, следя чтобы в хвосте получалось новое число, а если не получается, возвращаться к предыдущему символу
У Вас M^N шагов, и на каждом из них возможно до N вариантов выбора следующего символа. Это же сколько вариантов придётся перебрать?

Добавлено через 4 минуты
Цитата Сообщение от SlavaSSU Посмотреть сообщение
это ж гуглится. "shortest common superstring problem".
Нужна не кратчайшая, а минимальная последовательность
0
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
26.01.2016, 14:21 7
Shamil1, 1) на хабре про подстроки
2) ?
3) если нужна минимальная, то кажется можно просто посортить и в этом порядке добавлять. Но в этом случае ответ на n=2, m=2 00+01+10+11(00011011 < 00110).
0
90 / 87 / 11
Регистрация: 20.11.2008
Сообщений: 724
26.01.2016, 15:40 8
Цитата Сообщение от Shamil1 Посмотреть сообщение
У Вас M^N шагов, и на каждом из них возможно до N вариантов выбора следующего символа. Это же сколько вариантов придётся перебрать?
На Lua при N=M=5 находит за 5 секунд:
последовательность
Кликните здесь для просмотра всего текста
00000100002000030000400011000120001300014000210002 20002300024000310003200033000340004100042000430004 40010100102001030010400111001120011300114001210012 20012300124001310013200133001340014100142001430014 40020100202002030020400211002120021300214002210022 20022300224002310023200233002340024100242002430024 40030100302003030030400311003120031300314003210032 20032300324003310033200333003340034100342003430034 40040100402004030040400411004120041300414004210042 20042300424004310043200433004340044100442004430044 40101101012010130101401021010220102301024010310103 20103301034010410104201043010440110201103011040111 10111201113011140112101122011230112401131011320113 30113401141011420114301144012020120301204012110121 20121301214012210122201223012240123101232012330123 40124101242012430124401302013030130401311013120131 30131401321013220132301324013310133201333013340134 10134201343013440140201403014040141101412014130141 40142101422014230142401431014320143301434014410144 20144301444020210202202023020240203102032020330203 40204102042020430204402103021040211102112021130211 40212102122021230212402131021320213302134021410214 20214302144022030220402211022120221302214022210222 20222302224022310223202233022340224102242022430224 40230302304023110231202313023140232102322023230232 40233102332023330233402341023420234302344024030240 40241102412024130241402421024220242302424024310243 20243302434024410244202443024440303103032030330303 40304103042030430304403104031110311203113031140312 10312203123031240313103132031330313403141031420314 30314403204032110321203213032140322103222032230322 40323103232032330323403241032420324303244033040331 10331203313033140332103322033230332403331033320333 30333403341033420334303344034040341103412034130341 40342103422034230342403431034320343303434034410344 20344303444040410404204043040440411104112041130411 40412104122041230412404131041320413304134041410414 20414304144042110421204213042140422104222042230422 40423104232042330423404241042420424304244043110431 20431304314043210432204323043240433104332043330433 40434104342043430434404411044120441304414044210442 20442304424044310443204433044340444104442044430444 41111121111311114111221112311124111321113311134111 42111431114411212112131121411222112231122411232112 33112341124211243112441131211313113141132211323113 24113321133311334113421134311344114121141311414114 22114231142411432114331143411442114431144412122121 23121241213212133121341214212143121441221312214122 22122231222412232122331223412242122431224412313123 14123221232312324123321233312334123421234312344124 13124141242212423124241243212433124341244212443124 44131321313313134131421314313144132141322213223132 24132321323313234132421324313244133141332213323133 24133321333313334133421334313344134141342213423134 24134321343313434134421344313444141421414314144142 22142231422414232142331423414242142431424414322143 23143241433214333143341434214343143441442214423144 24144321443314434144421444314444222223222242223322 23422243222442232322324223332233422343223442242322 42422433224342244322444232332323423243232442332423 33323334233432334423424234332343423443234442424324 24424333243342434324344244332443424443244443333343 33443343433444343443444440000

код
Кликните здесь для просмотра всего текста

Код
--[[
Требуется найти минимально возможную последовательность цифр из системы счисления по основанию M, содержащую все N-значные числа включая числа с нулем в начале
https://www.cyberforum.ru/algorithms/thread1647320.html#post8670711
]]

--	основание
local m=5
--	количество
local n=5

--	результат
local row={}

local minL=m^n+n-1

--	использованные числа по их началам
local usedNumbers={}

local build
build=function(start,i)
	if i then
		table.insert(row,i-1)
		if #row==minL then
			print('Result!!!',table.concat(row))
			return true
		end
		start=start..i
	else
		start=start or ''
	end
	--print('try',table.concat(row))
	local un
	local c=#start
	if c>=n-1 then
		if c==n then
			start=start:sub(2)
		end
		un=usedNumbers[start]
		if not un then
			un={}
			usedNumbers[start]=un
		end
	end
	for i=1,n do
		if not un then
			if build(start,i) then
				return true
			end
		elseif not un[i] then
			un[i]=true
			if build(start,i) then
				return true
			end
			un[i]=false
		end
	end
	row[#row]=nil
end

build()
1
1542 / 637 / 84
Регистрация: 01.10.2012
Сообщений: 3,128
26.01.2016, 16:12 9
Типично бесполезная задачка, но интересно что в действительности цель вовсе не "найти минимальную" Нужна какая-то система/порядок чтобы автоматычно (и не используя память) отслеживать какие числа уже были. Иначе как только появляется что-то типа "table.insert" - все, хана уже на 8-ричной (если не раньше)
0
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,037
27.01.2016, 13:35  [ТС] 10
Цитата Сообщение от SlavaSSU Посмотреть сообщение
wingblack, это ж гуглится. "shortest common superstring problem". одна из ссылок будет везти на хабр - там простой жадный алгоритм описан.
Похоже это то что нужно, главное найти название проблемы )
Попробую, но не сильно уверен что точное решение будет считаться за допустимое количество времени.
Цитата Сообщение от Shamil1 Посмотреть сообщение
Цитата Сообщение от SlavaSSU
Посмотреть сообщение
это ж гуглится. "shortest common superstring problem".
Нужна не кратчайшая, а минимальная последовательность
Здесь цифры = буквы, и оценка ответа производится по количеству таких букв в тексте. Кратчайшая = минимальная. Разве нет?

Цитата Сообщение от Igor3D Посмотреть сообщение
Типично бесполезная задачка, но интересно что в действительности цель вовсе не "найти минимальную"
Мне сложно найти реальные условия при которых решение задачи будет полезно. Есть теоретическая ситуация по подбору пароля в устройстве, которое отпирается если нажали N клавиш в нужной последовательности и нужно минимизировать перебор.
0
Модератор
2959 / 2098 / 450
Регистрация: 26.03.2015
Сообщений: 8,148
27.01.2016, 14:05 11
Цитата Сообщение от wingblack Посмотреть сообщение
Кратчайшая = минимальная. Разве нет?
Кратчайших может быть несколько, а минимальная всегда одна.
0
90 / 87 / 11
Регистрация: 20.11.2008
Сообщений: 724
27.01.2016, 14:57 12
Цитата Сообщение от wingblack Посмотреть сообщение
Попробую, но не сильно уверен что точное решение будет считаться за допустимое количество времени.
тот вариант, что я предложил быстро работает, т.к. по факту перебор не получается полным. Для случая M=5=5 при длине ответа в 3129 символов происходит только 40 возвратов к предыдущему символу; а при M=6=6 ответ длинной 46661 находится за 46661 + 75 вызовов функции build
0
Модератор
2959 / 2098 / 450
Регистрация: 26.03.2015
Сообщений: 8,148
27.01.2016, 17:57 13
Цитата Сообщение от ProgJ Посмотреть сообщение
На Lua при N=M=5 находит за 5 секунд:
миллисекунд?

Цитата Сообщение от ProgJ Посмотреть сообщение
код
У Вас в коде есть стилистическая ошибка: код инициализации помещён внутри цикла. Вместо того, чтобы нормально инициализировать данные, Вы на каждом шаге делаете проверки. И тут дело не столько в лишних затратах времени, сколько в плохой читаемости кода.
Вот так было бы гораздо нагляднее:
Код
--[[
Требуется найти минимально возможную последовательность цифр из системы счисления по основанию M, содержащую все N-значные числа включая числа с нулем в начале
https://www.cyberforum.ru/algorithms/thread1647320.html#post8670711
]]
 
--  основание
local m=3
--  количество
local n=3
 
--  результат
local row={}
 
local minL=m^n+n-1
 
--  использованные числа по их началам
local usedNumbers={}

local build
build=function(start,i)
    table.insert(row,i-1)
    if #row==minL then
        print('Result!!!',table.concat(row))
        return true
    end
    start=start..i
    start=start:sub(2)
    --print('try',table.concat(row))
    local un=usedNumbers[start]
    if not un then
        un={}
        usedNumbers[start]=un
    end
    for i=1,n do
        if not un[i] then
            un[i]=true
            if build(start,i) then
                return true
            end
            un[i]=false
        end
    end
    row[#row]=nil
end

for j=1,n-2 do table.insert(row,0) end 
build( string.rep('1', n-1), 1)
http://ideone.com/32K3gf
0
90 / 87 / 11
Регистрация: 20.11.2008
Сообщений: 724
27.01.2016, 19:28 14
Цитата Сообщение от Shamil1 Посмотреть сообщение
миллисекунд?
нет, было больше четырёх секунд в тот раз, может быть IDE как раз начала мусор собирать или ещё что-то. На самом деле считает за 0.016 секунд

Цитата Сообщение от Shamil1 Посмотреть сообщение
У Вас в коде есть стилистическая ошибка: код инициализации помещён внутри цикла.
Спасибо. Да, я извернулся, но сделал это намеренно. Откуда вы знаете, что результат будет начинаться с нулей? Теперь мы это знаем, но сначала я не был уверен даже, что минимальная последовательность есть всегда. Поэтому я рассматривал случай, когда алгоритм будет менять и первые символы последовательности
А исправить в коде стоит строчку с циклом for i=1,n do должно быть for i=1,m do
Ещё можно избавится от рекурсии, чтоб работало с бОльшими значениями
0
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,037
27.01.2016, 20:36  [ТС] 15
Цитата Сообщение от ProgJ Посмотреть сообщение
тот вариант, что я предложил быстро работает, т.к. по факту перебор не получается полным. Для случая M=5=5 при длине ответа в 3129 символов происходит только 40 возвратов к предыдущему символу; а при M=6=6 ответ длинной 46661 находится за 46661 + 75 вызовов функции build
Если N = 1 или 2 вообще ничего не выводит
Запустил на N=5 M=6 - сидит думает
Использую последний Lua52 x32 под винду c оф сайт
Попробуй для основания 10 и длинны 4

Добавлено через 3 минуты
Цитата Сообщение от Shamil1 Посмотреть сообщение
Кратчайших может быть несколько, а минимальная всегда одна.
Можно увидеть что вы понимаете под кратчайшей, а что под минимальной? В рамках данной задачи для меня это синонимы, так как не имеет смысла считать ответ неким числом.
0
Модератор
2959 / 2098 / 450
Регистрация: 26.03.2015
Сообщений: 8,148
27.01.2016, 21:18 16
Цитата Сообщение от wingblack Посмотреть сообщение
В рамках данной задачи для меня это синонимы
Тогда надо писать "найти любую из кратчайших".

Добавлено через 7 минут
Цитата Сообщение от ProgJ Посмотреть сообщение
Откуда вы знаете, что результат будет начинаться с нулей?
Это было понятно с самого начала. В числе должны быть где-то n нулей подряд. Если мы ищем самое маленькое, то они будут в начале.

Цитата Сообщение от ProgJ Посмотреть сообщение
Поэтому я рассматривал случай, когда алгоритм будет менять и первые символы последовательности
Значит, надо было сделать отдельную функцию для инициализации, которая будет перебирать все варианты для первых n-1 символов.

Цитата Сообщение от ProgJ Посмотреть сообщение
А исправить в коде стоит строчку с циклом for i=1,n do должно быть for i=1,m do
Ещё можно избавится от рекурсии, чтоб работало с бОльшими значениями
Да. Ещё можно (в ущерб скорости) избавиться от usedNumbers.

Добавлено через 1 минуту
Перевёл на C#
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void Main()
{
    Solve(7,4);
}
 
void Solve(int n, int m) 
{
    int minL = (int)Math.Pow(m, n) + n - 1;
    List<int> row = new List<int>(minL);
    for(int j = 0; j < n-2; j++)
        row.Add(0);
    Dictionary<string, bool[]> usedNumbers = new Dictionary<string, bool[]>();
        
    Func<string, int, bool> build = null;
    build = (start, i) => {
        row.Add(i);
        if(row.Count == minL)
            return true;
        start = (start + i).Substring(1);
        bool[] un = null;
        if(!usedNumbers.TryGetValue(start, out un))
            usedNumbers[start] = un = new bool[n+1];
        for(i = 0; i < m; i++)
            if(!un[i])
            {
                un[i] = true;
                if(build(start,i))
                    return true;
                un[i] = false;
            }
        row.RemoveAt(row.Count - 1);
        return false;
    };
        
    build(new string('0', n-1), 0);
    Console.WriteLine(string.Join("", row.Select(x => x.ToString()).ToArray()));
}
1
90 / 87 / 11
Регистрация: 20.11.2008
Сообщений: 724
27.01.2016, 21:43 17
Цитата Сообщение от wingblack Посмотреть сообщение
Если N = 1 или 2 вообще ничего не выводит
должно
Цитата Сообщение от wingblack Посмотреть сообщение
Запустил на N=5 M=6 - сидит думает
а так не должно быть, должно или быстро выдавать ответ или вываливаться из-за нехватки Lua-стека. У вас цикл до m?
Цитата Сообщение от wingblack Посмотреть сообщение
Попробуй для основания 10 и длинны 4
для основания 10 программа не работает, нужно менять способ заполнения usedNumbers
Цитата Сообщение от Shamil1 Посмотреть сообщение
В числе должны быть где-то n нулей подряд. Если мы ищем самое маленькое, то они будут в начале.
мы ищем минимальную последовательность, т.е. самое короткое число
Цитата Сообщение от Shamil1 Посмотреть сообщение
Значит, надо было сделать отдельную функцию для инициализации, которая будет перебирать все варианты для первых n-1 символов.
Это уже усложнение программы. По мне проще написать комментарии к каждой строчке, чем ваш способ

А вообще, я набросал код только для того, чтоб проверить гипотезу о достижимости длинны в m^n+n-1 символов
0
1542 / 637 / 84
Регистрация: 01.10.2012
Сообщений: 3,128
28.01.2016, 08:19 18
А если дерево (забыл как называется, не раз упоминалось при поиске строк). Вернее M (число цифр) деревьев
0
Модератор
2959 / 2098 / 450
Регистрация: 26.03.2015
Сообщений: 8,148
28.01.2016, 18:32 19
Заменил словарь на массив (для ускорения работы), а булевы массивы внутри него на целые числа (для экономии памяти).
Заменил рекурсию циклом.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void Solve2(int n, int m) 
{
    int minL = (int)Math.Pow(m, n) + n - 1;
    List<int> row = new List<int>(Enumerable.Repeat(0, n-1)) { Capacity = minL };
    int[] usedNumbers = new int[minL/m];
    
    string start = new string('0', n-1);
    int id = 0; // index in usedNumbers
    int i = 0; // current digit
    for(;;)
    {
        if(i >= m)
        {
            i = row[row.Count - 1];
            row.RemoveAt(row.Count - 1);
            start = (row[row.Count - n + 1] + start);
            start = start.Substring(0, start.Length - 1);
            id = start.Aggregate(0, (acc,c) => acc*m + (c - '0'));
            usedNumbers[id] &= ~(1 << i);
            i++;
            continue; // go to the parent
        }
    
        int bit = 1 << i;
        if((usedNumbers[id] & bit) == 0)
        {
            row.Add(i);
            if(row.Count == minL)
                break;
            usedNumbers[id] |= bit;
            start = (start + i).Substring(1);
            id = start.Aggregate(0, (acc,c) => acc*m + (c - '0'));
            i = 0;
            continue; // go to the first child
        }
        
        i++; // go to the next sibling
    }
 
    Console.WriteLine(row.Count);
    Console.WriteLine(row.Aggregate(new StringBuilder(row.Count), (acc,c) => acc.Append(c) ).ToString() );
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.01.2016, 18:32
Помогаю со студенческими работами здесь

Найти все N-*значные числа, у которых сумма цифр равна их произведению
Доброго времени суток! Помогите пожалуйста, сам не знаю как сделать! Нужно найти все N-*значные...

Найти все n-значные числа, сумма квадратов цифр которых кратна М
Найти все n-значные числа, сумма квадратов цифр которых кратна М.

Найти все натуральные n-значные числа, цифры в которых образуют строго возрастающую последовательность
Ребят,помогите сделать эту задачу через массивы.Я сделал через строки но мне сказали переделать ее...

Найти все натуральные n-значные числа, цифры в которых образуют строго возрастающую последовательность
Найти все натуральные n-значные числа, цифры в которых образуют строго возрастающую...

Найти все натуральные n-значные числа, цифры в которых образуют строго возрастающую последовательность
найти все натуральные n-значные числа, цифры в которых образуют строго возрастающую...

Найти все натуральные n-значные числа, цифры в которых образуют строго возврастающую последовательность
Найти все натуральные n-значные числа, цифры в которых образуют строго возврастающую...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru