Как сделать перебор всех символов от 1 до заданной длины?

Question

[chaostoken]

мне надо все комбинации букв и сочетания. например есть последовательность "абв" и максимальное количество символов 4. я хочу
а
б
в
aa
аб
ав
ба
бб
бв
....
ввва
вввб
вввв

Тоесть типа

func validCombinations(alphabet string, maxChar int) bool {
    
}

// передаем возможные символы и максимальную длину
validCombinations("абв", 4)

и функция проходит по всем комбинациям

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

Понимаю что тут два варианта - рекурсия или цикл. я бы очень хотел реализовать в цикле без рекурсии. важна производительность

PS. пока есть такая жуткая реализация которую сам сочинил. получается я что то вроде собственной системы счисления делаю и перевожу цифры в символы

func checkCombinations(alphabet string, length int)  {
	countChars := len(alphabet)
	elems := make([]string, countChars)
	for i, r := range alphabet {
		elems[i] = string(r)
	}
	var current int
	base := float64(countChars)
	baseLog := math.Log(float64(countChars))
	for float64(current) < math.Pow(base, float64(length)) {
		if current < countChars {
			println(elems[current])
		} else {
			var combo string
			x := float64(current)
			size := int(math.Log(float64(current)) / baseLog)
			for size >= 0 {
				oneReg := math.Pow(base, float64(size))
				number := int(x / oneReg)
				x = x - oneReg*float64(number)
				combo = combo + elems[number]
				size--
			}
			println(combo)
		}
		current++
	}
}

Comments

[uvelichitel]

func validCombinations(alphabet string, maxChar int) bool

А что эта функция должна возвращать?

[chaostoken]

uvelichitel, это не так важно. добавить ретурн я смогу. мне важно для начала просто пройтись по всем комбинациям и хотя бы fmt.Println сделать чтоб убедиться что в правильном порядке все идет

Answer 1

[uvelichitel]

Ну например вот так можно https://play.golang.org/p/0Jnt-ONC7XO
Немного динамического программирования) Будем переиспользовать результаты уже сделанных вычислений

func validCombinations(alphabet string, maxChar int) []string {
	var result []string = []string{""}
	var last, next int
	for i := 1; i <= maxChar; i++ {
		last = len(result)
		for _, str := range result[next:] {
			for _, char := range alphabet {
				result = append(result, str+string(char))
			}
		}
		next = last
	}
	return result
}

Comments

[chaostoken]

спасибо. есть вопрос. а если я не хочу вычислять все комбинации сразу. я хочу получать их по одной и работать по одной. не хочу все сразу в память засаживать. может их 100000000000000000000000000000000000000000000000000000000000000000000000000000000000. что в таком случае?

Answer 2

[Lynn «Кофеман»]

Что бы не вычислять все комбинации сразу, поиграем со шрифтами каналами:

func main() {
	ch := GenerateAllPerms("абв", 4)
	i := 1
	for s := range ch {
		fmt.Println(i, s)
		i++
	}
}

// GeneratePermsN выдаёт в канал все комбинации длины n
func GeneratePermsN(ch chan string, chars []string, prefix string, n int) {
	for _, char := range chars {
		str := prefix + char
		if n == 1 {
			ch <- str
		} else {
			GeneratePermsN(ch, chars, str, n-1)
		}
	}
}

// GenerateAllPerms возвращает канал в который будут записаны все комбинации длины от 1 до n
func GenerateAllPerms(alphabet string, n int) chan string {
	ch := make(chan string)
	chars := strings.Split(alphabet, "")
	go func() {
		for i := 1; i <= n; i++ {
			GeneratePermsN(ch, chars, "", i)
		}
		close(ch)
	}()
	return ch
}

P.S. Наверняка этот код можно улучшить, т.к. на Go я начал учить на этих январских праздниках =)