Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Перебор комбинаций (помогите реализовать цикл)

19K
30 июня 2008 года
lobZik
2 / / 08.08.2006
Не хватает мозгу, помогите в реализации
Допустим есть слово "123", есть ограничитель длинны получаемых комбинаций - 2 и мы должны сформировать все возможные варианты перебора комбинаций длина_слова в степени степень

Пример:
"123" - 2

11
12
13
21
22
23
31
32
33

зы: Возможно следует использовать рекурсию, но с ней я не оч дружу.

[color=red]Для тех, у кого "не хватает мозгу", у нас есть специальный раздел - "студенты", куда и переезжает твоя тема, а в след. раз будет просто удалена. Злой зеленый модератор.[/color]
9.5K
30 июня 2008 года
ROLpogo
80 / / 22.08.2006
Код:
#include <string.h>
#include <math.h>
#include <stdio.h>


void FillDim(char* sValue, int CodeLen, char** sDim)
{
  int  CharsetLen = strlen(sValue),
       CodeCount  = pow(CharsetLen, CodeLen),
       Index;

  for (int i = 0; i < CodeLen; i++)
    for (int j = 0; j < CodeCount; j++)
    {
      Index = j / (CodeCount / pow(CharsetLen, (i + 1)));
      if ( Index >= CharsetLen )
        Index = Index % CharsetLen;
      sDim[j] = sValue[Index];
    }
}

void main()
{
  char  sCharSet[40];
  int   CodeLen;
  printf("Enter charset: ");
  scanf("%s", sCharSet);
  printf("Enter num of digit: ");
  scanf("%i", &CodeLen);

  int  CharsetLen = strlen(sCharSet),
       CodeCount  = pow(CharsetLen, CodeLen);

  char **sDim = new char*[CodeCount];
  for (int i = 0; i < CodeCount; i++)
    sDim = new char[CodeLen];
  FillDim(sCharSet, CodeLen, sDim);

  // Забили массив кодами, теперь, например, можно его залить в файл.

  FILE *pF;
  pF = fopen("C:\\CodeList.txt", "wt");
  char  sCode[42];
  for (int i = 0; i < CodeCount; i++)
  {
    sCode[0] = 0;
    for (int j = 0; j < CodeLen; j++)
      sCode[j] = sDim[j];
    sCode[CodeLen    ] = '\n';
    sCode[CodeLen + 1] = '\0';
    fputs(sCode, pF);
  }
  fclose(pF);

  for (int i = 0; i < CodeCount; i++)
    delete []sDim;
  delete []sDim;
}


Только не переусердствуй. 10 знаковый набор кодов из строки 0123456789 потянет ~ на 111 Гб на винте, и это если ещё оперативка потянет :)

Попробовал сгенерить 7-ми значные коды из 0123456789.
Проц AMD 3 ГГц х 2, 2 Гб ОЗУ. Во время работы программа съела ~1 Гб оперативки, 50% процессорного времени и сгенерила файл на ~ 87 Mb.
4.3K
30 июня 2008 года
flat
142 / / 27.12.2005
Предложу свой вариант:
Код:
void recursion(int index, int pow, string & str, string & word, set<string> & str_set)
{
    if (index == pow)
        str_set.insert(word);
    else
        for (int i = 0; i < str.size(); i++)
        {
            word[index] = str;
            recursion(index + 1, pow, str, word, str_set);
        }
}

void combinations(string str, int pow, set<string> & str_set)
{
    int str_len = str.size();
    if (pow > str_len || pow <= 0)
        return;
    string word;
    word.resize(pow);
    recursion(0, pow, str, word, str_set);
}

int main()
{
    set<string> str_set;
    combinations("123", 2, str_set);
    ostream_iterator<string, char> out_iter(cout, "\n");
    copy(str_set.begin(), str_set.end(), out_iter);

    return 0;
}
505
01 июля 2008 года
vAC
343 / / 28.02.2006
Код:
[SIZE=2][COLOR=#0000ff]#include [/COLOR][/SIZE][SIZE=2][COLOR=#800080]<iostream>[/COLOR][/SIZE]
[SIZE=2][COLOR=#0000ff]#include [/COLOR][/SIZE][SIZE=2][COLOR=#800080]<vector>[/COLOR][/SIZE]
[COLOR=#800080][/COLOR]
[SIZE=2][COLOR=#0000ff]using [/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]namespace [/COLOR][/SIZE][SIZE=2][COLOR=#010001]std[/COLOR][/SIZE][SIZE=2];[/SIZE]
 
[SIZE=2][COLOR=#0000ff]bool [/COLOR][/SIZE][SIZE=2][COLOR=#010001]index_increment[/COLOR][/SIZE][SIZE=2]([/SIZE][SIZE=2][COLOR=#010001]vector[/COLOR][/SIZE][SIZE=2]<[/SIZE][SIZE=2][COLOR=#010001]size_t[/COLOR][/SIZE][SIZE=2]> &[/SIZE][SIZE=2][COLOR=#010001]index[/COLOR][/SIZE][SIZE=2], [/SIZE][SIZE=2][COLOR=#010001]size_t [/COLOR][/SIZE][SIZE=2][COLOR=#010001]base[/COLOR][/SIZE][SIZE=2])[/SIZE]
[SIZE=2]{[/SIZE]
[SIZE=2][COLOR=#010001]vector[/COLOR][/SIZE][SIZE=2]<[/SIZE][SIZE=2][COLOR=#010001]size_t[/COLOR][/SIZE][SIZE=2]>::[/SIZE][SIZE=2][COLOR=#010001]iterator [/COLOR][/SIZE][SIZE=2][COLOR=#010001]it[/COLOR][/SIZE][SIZE=2] = [/SIZE][SIZE=2][COLOR=#010001]index[/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#010001]end[/COLOR][/SIZE][SIZE=2]() - [/SIZE][SIZE=2][COLOR=#008000]1[/COLOR][/SIZE][SIZE=2];[/SIZE]
[SIZE=2]  ++(*[/SIZE][SIZE=2][COLOR=#010001]it[/COLOR][/SIZE][SIZE=2]);[/SIZE]
[SIZE=2][COLOR=#0000ff]  while[/COLOR][/SIZE][SIZE=2] (*[/SIZE][SIZE=2][COLOR=#010001]it[/COLOR][/SIZE][SIZE=2] >= [/SIZE][SIZE=2][COLOR=#010001]base[/COLOR][/SIZE][SIZE=2])[/SIZE]
[SIZE=2]  {[/SIZE]
[SIZE=2]    (*[/SIZE][SIZE=2][COLOR=#010001]it[/COLOR][/SIZE][SIZE=2]) = [/SIZE][SIZE=2][COLOR=#008000]0[/COLOR][/SIZE][SIZE=2];[/SIZE]
[SIZE=2][COLOR=#0000ff]    if[/COLOR][/SIZE][SIZE=2] ([/SIZE][SIZE=2][COLOR=#010001]it[/COLOR][/SIZE][SIZE=2] == [/SIZE][SIZE=2][COLOR=#010001]index[/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#010001]begin[/COLOR][/SIZE][SIZE=2]()) [/SIZE][SIZE=2][COLOR=#0000ff]return [/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]false[/COLOR][/SIZE][SIZE=2];[/SIZE]
[SIZE=2]    ++(*(--[/SIZE][SIZE=2][COLOR=#010001]it[/COLOR][/SIZE][SIZE=2]));[/SIZE]
[SIZE=2]  }[/SIZE]
[SIZE=2][COLOR=#0000ff]  return [/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]true[/COLOR][/SIZE][SIZE=2];[/SIZE]
[SIZE=2]}[/SIZE]
 
[SIZE=2][COLOR=#0000ff]int [/COLOR][/SIZE][SIZE=2][COLOR=#010001]main[/COLOR][/SIZE][SIZE=2]()[/SIZE]
[SIZE=2]{[/SIZE]
[SIZE=2][COLOR=#0000ff]const [/COLOR][/SIZE][SIZE=2][COLOR=#010001]string [/COLOR][/SIZE][SIZE=2][COLOR=#010001]str_input[/COLOR][/SIZE][SIZE=2] = [/SIZE][SIZE=2][COLOR=#800080]"123"[/COLOR][/SIZE][SIZE=2];[/SIZE]
[SIZE=2][COLOR=#0000ff]const [/COLOR][/SIZE][SIZE=2][COLOR=#010001]size_t [/COLOR][/SIZE][SIZE=2][COLOR=#010001]power[/COLOR][/SIZE][SIZE=2] = [/SIZE][SIZE=2][COLOR=#008000]2[/COLOR][/SIZE][SIZE=2];[/SIZE]
[SIZE=2][COLOR=#010001]vector[/COLOR][/SIZE][SIZE=2]<[/SIZE][SIZE=2][COLOR=#010001]size_t[/COLOR][/SIZE][SIZE=2]> [/SIZE][SIZE=2][COLOR=#010001]index[/COLOR][/SIZE][SIZE=2]([/SIZE][SIZE=2][COLOR=#010001]power[/COLOR][/SIZE][SIZE=2]);[/SIZE]
[SIZE=2][COLOR=#010001]string [/COLOR][/SIZE][SIZE=2][COLOR=#010001]str_output[/COLOR][/SIZE][SIZE=2]([/SIZE][SIZE=2][COLOR=#010001]power[/COLOR][/SIZE][SIZE=2], [/SIZE][SIZE=2][COLOR=#008000]0[/COLOR][/SIZE][SIZE=2]);[/SIZE]
 
[SIZE=2][COLOR=#0000ff]  do[/COLOR][/SIZE][SIZE=2] {[/SIZE]
[SIZE=2][COLOR=#0000ff]    for[/COLOR][/SIZE][SIZE=2] ([/SIZE][SIZE=2][COLOR=#010001]size_t [/COLOR][/SIZE][SIZE=2][COLOR=#010001]i[/COLOR][/SIZE][SIZE=2] = [/SIZE][SIZE=2][COLOR=#008000]0[/COLOR][/SIZE][SIZE=2]; [/SIZE][SIZE=2][COLOR=#010001]i[/COLOR][/SIZE][SIZE=2] < [/SIZE][SIZE=2][COLOR=#010001]power[/COLOR][/SIZE][SIZE=2]; ++[/SIZE][SIZE=2][COLOR=#010001]i[/COLOR][/SIZE][SIZE=2])[/SIZE]
[SIZE=2][COLOR=#010001]      str_output[/COLOR][/SIZE][SIZE=2][[/SIZE][SIZE=2][COLOR=#010001]i[/COLOR][/SIZE][SIZE=2]] = [/SIZE][SIZE=2][COLOR=#010001]str_input[/COLOR][/SIZE][SIZE=2][[/SIZE][SIZE=2][COLOR=#010001]index[/COLOR][/SIZE][SIZE=2][[/SIZE][SIZE=2][COLOR=#010001]i[/COLOR][/SIZE][SIZE=2]]];[/SIZE]
[SIZE=2][COLOR=#010001]    cout[/COLOR][/SIZE][SIZE=2] << [/SIZE][SIZE=2][COLOR=#010001]str_output[/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#010001]c_str[/COLOR][/SIZE][SIZE=2]() << [/SIZE][SIZE=2][COLOR=#010001]endl[/COLOR][/SIZE][SIZE=2];[/SIZE]
[SIZE=2]  } [/SIZE][SIZE=2][COLOR=#0000ff]while[/COLOR][/SIZE][SIZE=2] ([/SIZE][SIZE=2][COLOR=#010001]index_increment[/COLOR][/SIZE][SIZE=2]([/SIZE][SIZE=2][COLOR=#010001]index[/COLOR][/SIZE][SIZE=2], [/SIZE][SIZE=2][COLOR=#010001]str_input[/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#010001]length[/COLOR][/SIZE][SIZE=2]()));[/SIZE]
[SIZE=2][COLOR=#0000ff]  return [/COLOR][/SIZE][SIZE=2][COLOR=#008000]0[/COLOR][/SIZE][SIZE=2];[/SIZE]
[SIZE=2]}[/SIZE]
5
01 июля 2008 года
hardcase
4.5K / / 09.08.2005
Цитата: lobZik
есть слово "123", есть ограничитель длинны получаемых комбинаций - 2 и мы должны сформировать все возможные варианты перебора комбинаций


А на C# это будет вот так:

Код:
class Program {

    static IEnumerable<string> Permutate(string set, int length) {
        if (length <= 1)
            foreach (char c in set)
                yield return c.ToString();
        else
            foreach (string p in Permutate(set, length - 1))
                foreach (char c in set)
                    yield return p + c;
    }

    static void Main(string[] args) {
        foreach (string s in Permutate("01", 4))
            Console.WriteLine(s);
        Console.ReadKey();
    }
}
Не бейте хардкейза ногами, иллюстрирую чисто алгоритм.
431
01 июля 2008 года
sherry
207 / / 16.10.2006
lobZik
А язык, стало быть, не имеет значения?.. :)
320
01 июля 2008 года
m_Valery
1.0K / / 08.01.2007
Цитата: sherry
lobZik
А язык, стало быть, не имеет значения?.. :)



Поскольку тему перенесли из раздела С/С++/С# - язык какой то из этих трех.И автору ответили в 3-х вариантах...

431
02 июля 2008 года
sherry
207 / / 16.10.2006
m_Valery
Пардон, не знал о путешествии темы по разделам..
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог