How to enumerate all possible combinations of characters?

Question

Delphi

In general, the essence of the issue is this. How to iterate and output all possible combinations based on the available characters?
The number of characters is not known in advance.
It is possible on delphi, c ++.
For example, I have characters: "a,b,c". How to do a search so that it gives me:
a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
aab
aac
aba
abc
...
Thank you.

Answer 1

It begs the option to present the resulting strings with records in the N-ary number system, where the given letters are numbers from 0 to N-1, then the task is reduced to the output of single-digit numbers from 0 to N-1, two-digit numbers from 0 to N²-1, three-digit numbers from 0 up to N³-1. The N-ary notation is easy to obtain using the remainder and division.

#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'}));
}

The second option is to present these lines as a number record in a special number system without zero - with digits from 1 to N. In this case, it is easy to convert such a record into a number - ∑aᵢ × Nⁱ, but the inverse transformation should take into account that we do not have zero, then if the remainder turned out to be zero, the digit must be taken N.
Unlike the first option, there are no separate cycles for single-digit, two-digit and three-digit entries, since the results are in a row, "c" is followed by "aa", after "cc "- "aaa", and so on.

#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' }));
}

For a snack, how the same problem is solved in Haskell:

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

Answer 2

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

Answer 3

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

Answer 4

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

#! /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][email protected]$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;
#}