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

Question

[2slide]

В общем суть вопроса такова. Как сделать перебор и вывод всех возможных комбинаций на основе имеющихся символов?
Количество символов заранее не известно.
Можно на delphi, c++.
Например, у меня есть символы : "a,b,c". Как сделать перебор, чтобы мне выдало:
a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
aab
aac
aba
abc
...
Спасибо.

Comments

[Александр Ручкин]

А "aaaa", "aaab" надо? И почему?

[2slide]

Нужно все возможные варианты 5-10 символов. "sfdfs"...

Answer 1

[Александр Ручкин]

Напрашивается вариант представить результирующие строки записями в N-ричной системе счисления, где заданные буквы есть цифры от 0 до N-1, тогда задача сводится к выводу однозначных чисел от 0 до N-1, двузначных от 0 до N²-1, трёхзначных от 0 до N³-1. Запись в N-ричной системе легко получить, используя остаток от деления и деление.

#include <vector>

std::string gen(std::vector<char> alphabet, std::size_t idx, std::size_t digits)
{
	std::string ret(digits, alphabet[0]);

	std::size_t alphas = alphabet.size();
	while (digits--)
	{
		ret[digits] = alphabet[idx % alphas];
		idx /= alphas;
	}
	return ret;
}

void gen_and_out(std::size_t n, std::vector<char> alphabet)
{
	std::size_t numbers = 1;
	std::size_t alphas = alphabet.size();
	for (std::size_t i = 0; i < n; ++i)
	{
		numbers *= alphas; // на каждом шаге чисел в alphas раз больше
		for (std::size_t cur = 0; cur < numbers; ++cur)
		{
			std::cout << gen(alphabet, cur, i + 1) << std::endl;
		}
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	gen_and_out(3, std::vector<char>({ 'a', 'b', 'c'}));
}

Второй вариант - это представить эти строки как запись числа в особой системе счисления без нуля - с цифрами от 1 до N. В этом случае легко преобразовать такую запись в число - ∑aᵢ×Nⁱ, а вот обратное преобразование должно учитывать, что у нас нет нуля, тогда если остаток получился равным нулю, цифру нужно взять N.
В отличие от первого варианта, здесь нет отдельных циклов для однозначной, двузначной и трёхзначных записей, так как результаты идут подряд, за "c" следует "aa", за "cc" - "aaa", и так далее.

#include <vector>

std::string gen(std::vector<char> alphabet, std::size_t idx)
{
	std::vector<char> ret;

	std::size_t alphas = alphabet.size();

	while (idx)
	{
		std::size_t cur = idx % alphas;
		if (!cur) // нет нуля
			cur = alphas;
		ret.push_back(alphabet[cur - 1]);
		idx = (idx - cur) / alphas;
	}

	return std::string(ret.rbegin(), ret.rend());
}

void gen_and_out(std::size_t n, std::vector<char> alphabet)
{
	std::size_t numbers = 1;
	std::size_t alphas = alphabet.size();
	for (std::size_t i = 0; i < n; ++i)
	{
		numbers *= alphas;
		numbers += 1;
	}
	for (std::size_t i = 1; i < numbers; ++i)
		std::cout << gen(alphabet, i) << std::endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
	gen_and_out(3, std::vector<char>({ 'a', 'b', 'c' }));
}

На закуску, как та же задача решается на Haskell:

gen alphas n = concatMap (`replicateM` alphas) [1..n]
main = mapM_ putStrLn $ gen "abc" 3

Answer 2

[gleb_kudr]

Простой рекурсивный алгоритм, например.

Answer 3

[Сергей Протько]

www.programminglogic.com/powerset-algorithm-in-c

Comments

[Александр Ручкин]

И это явно не то, что требуется

[Сергей Протько]

@VoidEx сори, то пермутации. Обновил ответ.

[jackroll]

вау, офигенный алгоритм :))

[Александр Ручкин]

Это то же не то, там нет {1, 1, 1, 1}, {1, 1, 1, 2} и т.п., хотя, возможно, его можно модифицировать?

[Сергей Протько]

@VoidEx да что ж такое то... я что-то совсем не внимательный сегодня. Модифицировать его можно, в итоге все-равно имеем довольно простой рекурсивный алгоритм. Но конкретно этот сложно...

[jackroll]

VoidEx, ну да, string abc = "abc"; //массив символов же.

[Александр Ручкин]

@jackroll не понял ответа, речь о том, что тот алгоритм не сгенерирует "aaa", а должен.

Answer 4

[Anastasiya Sila]

Надеюсь на перле вам подойдет. Только недавно делала, правда он циферный..

#! /usr/bin/perl 

use strict;
use warnings;
use Fcntl;

#my $num=5;
#my @str=();


sub nextShuffle($)
{	my $shuffle=shift;
	for(my $i=1; $i<@$shuffle; $i++)
	{
		if($shuffle->[$i]<$i)
		{
			$shuffle->[$i]++;
			return $shuffle;
		}
		else
		{
			$shuffle->[$i]=0;
		}
	}
	return;
}

sub nextPermutation($)
{
	my $p=shift;
	my $i=$#$p-1;
	$i-- while $i>=0 and $p->[$i]>$p->[$i+1];
	if($i>=0)
	{
		my $j=$i+1;
		$j++ while $j<$#$p and $p->[$j+1]>$p->[$i];
		@$p[$i, $j]=@$p[$j, $i];
		push @$p, reverse splice @$p, $i+1;
		return $p;
	}
	return;
}

sub fact{
    my $n = shift;
    if ($n==0) {
        return 1;
    } else {
        return $n*fact($n-1);
    }
}

my $fileout = 'out.txt';
open(my $fo, '>>:encoding(UTF-8)', $fileout)
or die "Could not open file '$fileout' $!";

my $n=shift;
print $fo fact($n)."\n";
die "$0: Нужно неотрицательное число!\n" unless defined($n) and $n>=0;

for(my $p=[1..$n]; defined $p; $p=nextPermutation($p))
{
	print $fo "@$p\n";
}
#for (my $i=1; $i<$num; $i++){
#	$str[$i]=$i;
#}