Что нового

Перебор комбинаций из неск. элементов, и объединение их в последовательность

LightDemon

Новичок
Сообщения
24
Репутация
1
Заданы переменные A, B и C. Нужно создать все возможные комбинации этих переменных из N-элементов, при этом количество переменных в комбинации может быть от 0 до N. Из этих комбинаций убрать все комбинации которые содержат комбинацию АВ и ВС, и записать их в наиболее короткую единую последовательность, по возможности объединяя комбинации у которых конец одной комбинации совпадает с началом другой, например объединяя АА, АС, и СА, последовательность будет ААСА, а объединяя ААА, ААС, АСА, последовательность будет АААСА. Пример работы программы при N=2:
[box title=TitleBox]
Возможные комбинации:
AA
AB - не подходит по условию
AC
BA
BB
BC - не подходит по условию
CA
CB
CC
Правильная последовательность:
CAACCBBA
[/box]
 

C2H5OH

AutoIT Гуру
Сообщения
1,473
Репутация
333
Задача поставлена некорректно.
Приведенная в примере "правильная" последовательность не подходит по условию объединения комбинаций - объдиняя СА с АС, АС с СВ, СВ с БА, мы должны получить САСВА вместо того что нам представленно как "правильная" последовательность.

Подумайте сначала хорошенько что же Вам нужно...
 
Автор
L

LightDemon

Новичок
Сообщения
24
Репутация
1
Задача поставлена вполне корректно, вариантов последовательности может быть несколько, но наша задача записать их в наиболее короткую единую последовательность, в приведенном примере соединение комбинаций происходит в порядке CA+AA+AC+CC+CB+BB+BA=CAACCBBA, и удовлетворяет всем условиям задачи.... По логике вещей если в получившейся последовательности взять любые идущие последовательно N-элементов, то они будут встречаться во всей последовательности единожды в данном порядке, но в этом я пока точно неуверен....
 

kaster

Мой Аватар, он лучший самый
Команда форума
Глобальный модератор
Сообщения
4,020
Репутация
624
OffTopic:
C2H5OH
тут без пол литра тебя не обойтись
 

C2H5OH

AutoIT Гуру
Сообщения
1,473
Репутация
333
По 50 грамм накатили - разобрался. :smile:
Вот это было лишнее:
и записать их в наиболее короткую единую последовательность, по возможности объединяя комбинации у которых конец одной комбинации совпадает с началом другой

Надо было написать: "Найти самую короткую строку, которая содержит все допустимые комбинации."
И всё. :D
 

C2H5OH

AutoIT Гуру
Сообщения
1,473
Репутация
333
Насколько я понимаю, это какая-то твоя лабораторная работа. Лучше бы ты сам разобрался, конечно, но если припекло...

Код:
; ABC
#include <Array.au3>

GLOBAL const $abc[3]=["A","B","C"]
GLOBAL const $n=2

DIM $combo[1]

_nalivay("")
GLOBAL $string_limit = $combo[0] * $n -3

$ono = _Budmo("")
MsgBox(4096, "pravilnaya stroka:", $ono)

Func _nalivay( $String1 )
	If StringInStr ( $String1, $abc[0] & $abc[1] ) > 0 Then Return
	If StringInStr ( $String1, $abc[1] & $abc[2] ) > 0 Then Return
	If StringLen($String1) > $n Then Return
	If StringLen($String1) = $n Then
		_ArrayAdd ($combo, $String1)
		$combo[0] += 1
	Else
		_nalivay( $String1 & $abc[0])
		_nalivay( $String1 & $abc[1])
		_nalivay( $String1 & $abc[2])
	EndIf
EndFunc

Func _Budmo( $string1 )

	Local $res = ""
	If StringLen($string1) > $string_limit Then Return $res

	Local $flag = 1
	for $i=1 to $combo[0]
		If StringInStr ( $string1, $combo[$i] ) = 0 Then $flag = 0
	Next
	If $flag = 1 Then Return $string1

	Local $l = $string_limit
	Local $l1
	for $i=0 to 2
		$String2 = _Budmo( $String1 & $abc[$i] )
		$l1 = StringLen($String2)
		If ($l1 > 0) AND ($l1 < $l) Then
			$res = $String2
			$l = $l1
		endif
	Next

	Return $res
EndFunc
 
Автор
L

LightDemon

Новичок
Сообщения
24
Репутация
1
Нет, это не лабораторная работа :smile: Задача придумана сама собой, для одной программки. Ваш код мне понравился, но загвоздка в том что время работы терпимо только при N=2, а в моем случае N<=10, но даже при N=3 машина думает дольше чем написать самому на листочке.....
 

C2H5OH

AutoIT Гуру
Сообщения
1,473
Репутация
333
Это задача перебора, она всегда связана с долгим временем работы.
Для ускорения процесса нужно подумать об ограничении длинны перебираемых цепочек.
Я взял в лоб:
если поставить в ряд ВСЕ комбинации символов и выбросить три исходных символа по правилу объединения комбинаций, то такая цепочка гарантированно будет удовлетворять условиям задачи.
Код:
GLOBAL $string_limit = $combo[0] * $n -3


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

Метод "написать на листочке" не даёт гарантированного результата. Вы уверены что не найдётся последовательность меньшей длинны? ;D
 
Верх