@chaostoken

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

мне надо все комбинации букв и сочетания. например есть последовательность "абв" и максимальное количество символов 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++
	}
}
  • Вопрос задан
  • 116 просмотров
Пригласить эксперта
Ответы на вопрос 2
uvelichitel
@uvelichitel Куратор тега Go
habrahabr.ru/users/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
}
Ответ написан
Lynn
@Lynn
nginx, js, css
Что бы не вычислять все комбинации сразу, поиграем со шрифтами каналами:

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 я начал учить на этих январских праздниках =)
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Lanck Telecom Санкт-Петербург
от 180 000 до 250 000 ₽
Leningrad Media Санкт-Петербург
До 200 000 ₽
28 февр. 2021, в 18:31
4000 руб./за проект
28 февр. 2021, в 17:59
500 руб./за проект
28 февр. 2021, в 17:56
16000 руб./за проект