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

[LightDemon]

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

 

[C2H5OH]

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

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

 

[LightDemon]

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

 

[kaster]

OffTopic:
C2H5OH
тут без пол литра тебя не обойтись

 

[C2H5OH]

По 50 грамм накатили - разобрался.
Вот это было лишнее:

и записать их в наиболее короткую единую последовательность, по возможности объединяя комбинации у которых конец одной комбинации совпадает с началом другой

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

 

[LightDemon]

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

именно так

 

[C2H5OH]

Насколько я понимаю, это какая-то твоя лабораторная работа. Лучше бы ты сам разобрался, конечно, но если припекло...

; 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

 

[LightDemon]

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

 

[C2H5OH]

Это задача перебора, она всегда связана с долгим временем работы.
Для ускорения процесса нужно подумать об ограничении длинны перебираемых цепочек.
Я взял в лоб:
если поставить в ряд ВСЕ комбинации символов и выбросить три исходных символа по правилу объединения комбинаций, то такая цепочка гарантированно будет удовлетворять условиям задачи.

GLOBAL $string_limit = $combo[0] * $n -3

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

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