Алгоритм возможных значений

Допустим у нас имеется массив array(1=>"1", 2=>"2", 3=>"3")
Алгоритм должен выдать следующее:
1
2
3
12
13
23
123
Нужен алгоритм??

Индекс элемента массива,равен значению элемента с этим индексом.Так

Цитата bizar @ 05.02.07, 12:35

Нужен алгоритм??

Алгоритм есть некая конечная последовательность выполнения инструкций,причем имеющая некую закономерность.

Цитата bizar @ 05.02.07, 12:35

1
2
3
12
13
23
123

Тут как я понимаю,есть закономерность.Некие сочитания.
В данном случае надо исходить из того,чего будет выше,затрат на написание алгоритма,или выгоды от него.

Если элементов надо выдать штук 10 000,то конечно пиши алгоритм.
Если 7,то нахрен надо морочится?
Юзеру наплевать как выполнена программа...

Вот как в принципе выглядит но алгоритмом записать не могу придумать.
Array (1=>"1", 2=>"2", 3=>"3", 4=>"4", 5=>"5")

1 2 3 4 5
 
12 13 14 15
23 24 25
34 35
45
 
123 124 125
234 235
345
 
1234 1235
2345
 
12345

Добавлено 05.02.07, 12:47

Цитата MakedoneZ @ 05.02.07, 12:43

Если элементов надо выдать штук 10 000,то конечно пиши алгоритм.
Если 7,то нахрен надо морочится?

Да, нужно будет 10 000.

for i := 0 to n-1 do
  for j := i + 1 to n do
    WriteLn(i,j);

Это для первого блока.

Сообщение отредактировано: MakedoneZ - 05.02.07, 12:52

Цитата bizar @ 05.02.07, 12:45

1 2 3 4 5

12 13 14 15
23 24 25
34 35
45

123 124 125
234 235
345

1234 1235
2345

12345

Это - что то из комбинаторикаи, если добавить несколько элементов (134, 135, 145, 245, 1245,1345). Однако, я ее забыл.

Поиск в ширину. Заводим очередь строк. Сначала забиваем в очередь даные символы. А потом на каждом шаге запоминаем текущую строку, а в очередь ложим все строки полученные путем прибавления в конец текущей строки поочередно одного из символов, которые следуют в начальном массиве после последнего в текущей строке.

Ок вот программа



int main() {


printf("1
2
3
12
13
23
123
");

Цитата MakedoneZ @ 05.02.07, 12:50

for i := 0 to n-1 do
for j := i + 1 to n do
WriteLn(i,j);



Это для первого блока.

Мне нужно что выставлялась для любого количества блоков.
Первое мы можем определять количество блоков.
А потом формировать это для каждого блока. Вопрос только как?

Добавлено 05.02.07, 13:24

Цитата Stratocoder @ 05.02.07, 13:20

Поиск в ширину. Заводим очередь строк. Сначала забиваем в очередь даные символы. А потом на каждом шаге запоминаем текущую строку, а в очередь ложим все строки полученные путем прибавления в конец текущей строки поочередно одного из символов, которые следуют в начальном массиве после последнего в текущей строке.

А программно показать можешь?

procedure GetCombs(n: Word);
var
  i,j,z: Word;
      h: ShortString;
 
begin
  h := '';
  for z := 1 to n do
    begin
      for i := z to n-1 do
        for j := i+1 to n do
          ShowMessage(h + IntToStr(i) + IntToStr(j));
      h := h + IntToStr(z);
    end;
end;

Проверь-ка...

Добавлено 05.02.07, 13:32
Черновой вариант...
Ща подправлю...

таких наборов для N элементов будет 2^N-1 (если не учитывать пустой набор), так что просто пробегаем в цикле от 1 до 2^N, на каждой итерации выводя те элементы из набора, для которых в счетчике цикла биты единичные.

Кривовато правда. Написал лишь бы работало - спешу.

#include <vector>
#include <map>
#include <string>
#include <iostream>
#include <queue>
 
using namespace std;
 
int main()
{
  vector< char > v;
  map< char, int > mp;
  int n;
  cin>>n;
  v.resize(n);
  for (int i = 0; i < n; ++i)
  {
    cin>>v[i];
    mp[v[i]] = i;
  }
  queue< string > q;
  for (int i = 0; i < v.size(); ++i)
    q.push(string() + v[i]);
  while(!q.empty())
  {
    string cur = q.front();
    q.pop();
    cout<<cur<<endl;
    for (int i = mp[cur[cur.size() - 1]] + 1; i < n; ++i)
      q.push(cur + v[i]);
  }
  return 0;
}

Добавлено 05.02.07, 13:44
Компилил на g++

мне на php надо в ++ не селён для чего библиотеки <vector> . . . <queue> не знаю.

Добавлено 05.02.07, 14:03

Цитата MakedoneZ @ 05.02.07, 13:31

procedure GetCombs(n: Word);
var
i,j,z: Word;
h: ShortString;

begin
h := '';
for z := 1 to n do
begin
for i := z to n-1 do
for j := i+1 to n do
ShowMessage(h + IntToStr(i) + IntToStr(j));
h := h + IntToStr(z);
end;
end;

Можно комент. я на php переделаю.

<vector> - по сути массив, можно заменить
<map> - ассоциативный массив, ставим в соответствие символу его индекс в массиве
<string> - строки... это понятно
<iostream> - ввод/вывод
<queue> - очередь

-Added 05.02.07, 14:09

Цитата MakedoneZ @ 05.02.07, 13:31

procedure GetCombs(n: Word);
var
  i,j,z: Word;
      h: ShortString;
 
begin
  h := '';
  for z := 1 to n do
    begin
      for i := z to n-1 do
        for j := i+1 to n do
          ShowMessage(h + IntToStr(i) + IntToStr(j));
      h := h + IntToStr(z);
    end;
end;

Это не может работать! Здесь надо использовать либо поиск в глубину, либо в ширину. А таким простым алгоритмом не отделаешься.

Сообщение отредактировано: Stratocoder - 05.02.07, 14:09

Цитата Stratocoder @ 05.02.07, 13:41

#include <vector>
#include <map>
#include <string>
#include <iostream>
#include <queue>

using namespace std;

int main()
{
vector< char > v;
map< char, int > mp;
int n;
cin>>n;
v.resize(n);
for (int i = 0; i < n; ++i)
{
cin>>v[i];
mp[v[i]] = i;
}
queue< string > q;
for (int i = 0; i < v.size(); ++i)
q.push(string() + v[i]);
while(!q.empty())
{
string cur = q.front();
q.pop();
cout<<cur<<endl;
for (int i = mp[cur[cur.size() - 1]] + 1; i < n; ++i)
q.push(cur + v[i]);
}
return 0;
}

Цитата Stratocoder @ 05.02.07, 14:03

<vector> - по сути массив, можно заменить
<map> - ассоциативный массив, ставим в соответствие символу его индекс в массиве
<string> - строки... это понятно
<iostream> - ввод/вывод
<queue> - очередь

Да сложновато разобраться в ++ , не так хорошо знаю программирование. Всёж благодарен. Теперь нужно это добро в php переделать но сначала разобрать что куда.

Цитата bizar @ 05.02.07, 14:19

Да сложновато разобраться в ++ , не так хорошо знаю программирование. Всёж благодарен. Теперь нужно это добро в php переделать но сначала разобрать что куда.

Вот вариант попроще (на Турбо Паскаль):

const
  n = 5;
 
var
  a: array[1..n] of char;
  i, j, k: integer;
  s: string[n];
 
begin
  for j:=1 to n do a[j]:=chr(ord('0')+j);
 
  for k:=1 to n do begin
    if (k=1) then begin
      write(a[1]); for j:=2 to n do write(' ', a[j]);
      writeln;
      end
    else begin
      for i:=1 to n-(k-1) do begin
        s:=''; for j:=i to i+(k-1) do s:=s+a[j]; write(s);
        for j:=k+i to n do begin
          s[k]:=a[j]; write(' ', s);
          end;
        writeln;
        end;
      end;
    writeln;
    end;
 
  readln;
end.

Делает именно то, что ты писал в #3.

Добавлено 06.02.07, 17:17

Цитата bizar @ 05.02.07, 14:00

Цитата (MakedoneZ @ Вчера, 16:31)

procedure GetCombs(n: Word);
...

Можно комент. я на php переделаю.

Можешь не париться - оно не то делает.

Сочетания они и есть. Конечно не в чистом виде
Только надо в цикле по i=1..n выводить все C_n^k в лексикографическом порядке.

bizar

Похожий вопрос здесь на форуме уже поднимался. Я тогда приводил (правда на другом форуме) такой алгоритм:
Как уже отметил MBo таких наборов будет 2^n – 1 (не считая 0).

Для n=5:

_____________________________________________________________
десятичные | двоичные | меняем  | заменяем        | результат
от  1      |          | порядок | значимый бит    |
до  2^n - 1|          | битов   | на его номер    |
           |          |         | (слева направо) |
___________|__________|_________|_________________|__________
       1   |    00001 |   10000 |        1....    |        1
       2   |    00010 |   01000 |        .2...    |        2
       3   |    00011 |   11000 |        12...    |       12
       4   |    00100 |   00100 |        ..3..    |        3
       5   |    00101 |   10100 |        1.3..    |       13
       6   |    00110 |   01100 |        .23..    |       23
       7   |    00111 |   11100 |        123..    |      123
       8   |    01000 |   00010 |        ...4.    |        4
       9   |    01001 |   10010 |        1..4.    |       14
      10   |    01010 |   01010 |        .2.4.    |       24
      11   |    01011 |   11010 |        12.4.    |      124
      12   |    01100 |   00110 |        ..34.    |       34
      13   |    01101 |   10110 |        1.34.    |      134
      14   |    01110 |   01110 |        .234.    |      234
      15   |    01111 |   11110 |        1234.    |     1234
      16   |    10000 |   00001 |        ....5    |        5
      17   |    10001 |   10001 |        1...5    |       15
      18   |    10010 |   01001 |        .2..5    |       25
      19   |    10011 |   11001 |        12..5    |      125
      20   |    10100 |   00101 |        ..3.5    |       35
      21   |    10101 |   10101 |        1.3.5    |      135
      22   |    10110 |   01101 |        .23.5    |      235
      23   |    10111 |   11101 |        123.5    |     1235
      24   |    11000 |   00011 |        ...45    |       45
      25   |    11001 |   10011 |        1..45    |      145
      26   |    11010 |   01011 |        .2.45    |      245
      27   |    11011 |   11011 |        12.45    |     1245
      28   |    11100 |   00111 |        ..345    |      345
      29   |    11101 |   10111 |        1.345    |     1345
      30   |    11110 |   01111 |        .2345    |     2345
      31   |    11111 |   11111 |        12345    |    12345

остается отсортировать по возрастанию.

function struktura_array($mas) {
$col_el = count($mas);
$col_zn = pow(2,$col_el)-1;
 
for ($i=1; $i <= $col_zn; $i++) {
 $dlina_i_bin = decbin($i);
 $zap_str = str_pad($dlina_i_bin, $col_el, "0", STR_PAD_LEFT);
 $zap_dop = strrev($zap_str);
 
 $dooh = array();
 for($j=0; $j < $col_el; $j++) {
 $dooh[] = $zap_dop[$j];
 }
 
 $d = 0; $a = '';
 foreach ($dooh as $k=>$v) {
    if ($v == 1) {$a[] .= $mas[$d];}
    $d++;
 }
 $return[] = $a;
}
 
return $return;
}

Aloha ну ты мэн то что надо +++

Цитата Stratocoder @ 05.02.07, 14:03

Это не может работать! Здесь надо использовать либо поиск в глубину, либо в ширину. А таким простым алгоритмом не отделаешься.

Не знаю, почему ты здесь называешь перебор поиском то ли в глубину, то ли в
ширину, но обойтись без использования очередей и ассоциативных массивов
можно запросто:

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
vector< char > v;
int n;
 
void rf(string s, int k, int i)
{
  if (k > 0)
    for (int j = i; j < (n-(k-1)); ++j)
      rf(s+v[j], k-1, j+1);
  else
    cout<<s<<endl;
}
 
int main()
{
  cout<<"n? "; cin>>n;
 
  v.resize(n);
  
  cout<<"v? ";
  for (int i = 0; i < n; ++i)
    сin>>v[i];
 
  for (int k = 1; k<=n; ++k)
    rf("", k, 0);
 
  v.resize(0);
  
  return 0;
}

Ку?

Цитата Bug Hunter @ 10.02.07, 21:08

Не знаю, почему ты здесь называешь перебор поиском то ли в глубину, то ли в
ширину, но обойтись без использования очередей и ассоциативных массивов
можно запросто

И как ты предлагаешь это называть??? Твой код реализует типичный поиск в глубину, а мой - в ширину.

всем привет!! времени прошло много, но, в целом, не помешает реализация алгоритма, предложенного Aloha, на Паскале (в Delphi)..

{            n
   +---+ = = = = = -------------
   |   |
   | 1 | 1 2 3 4 5
   |   |
   +---+------------------------
   |   |
   |   | 11 12 13 14 15
 m | 2 | 23 24 25
   |   | 34 35
   |   | 45
   |   |
   +---+------------------------
   |   |
   |   | 123 124 125 134 135 145
   | 3 | 234 235 245
   |   | 345
   |   |
   +---+------------------------}
 
uses
  SysUtils, Math;
 
const
  m = 3;     // количество знаков (см. рис.)
  n = 5;     // количество битов, т.е. используемых символов (см. рис.)
 
var
  i,         // количество чисел 1..2^n - 1
  j,         // количество битов 1..5
  k,         // количество знаков 1..3 (1 12 123)
  l,         // подсчет количества чисел
  c,         // подсчет количества знаков
  b: Word;   // значение бита 2^x ( 1 2 4 8 16 32 64 128 256 512)
  s: String;
 
begin
  l := Trunc(IntPower(2, n)) - 1; // 2^n - 1
 
  for k := 1 to m do              // массив выводимого количества символов, чтобы группировать по длине
 
  for i := 1 to l do begin        // массив количества чисел ( 2^n - 1)
    c := 0; s := '';
    for j := 0 to n-1 do begin    // массив количества битов
      b := Trunc(IntPower(2, j)); // 2^j
 
      if (i and b = 0) then       // проверка битов
        Continue;
 
      Inc(c);                     // увеличение количества знаков в строке
      s := s + IntToStr(j+1);     // формирование строки
    end;
 
    if (c <> k) then              // проверка длины
      Continue;
 
    Writeln(s);                   // вывод
  end;
 
  Readln;
end.

всех всем благ..

Сообщение отредактировано: azard - 21.07.10, 05:31