Форум на Исходниках.RU

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

azard — Wed, 21 Jul 2010 05:25:20 +0000

azard: всем привет!! времени прошло много, но, в целом, не помешает реализация алгоритма, предложенного 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.

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

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

Stratocoder — Sun, 11 Feb 2007 12:34:53 +0000

Stratocoder:

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

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

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

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

Bug Hunter — Sat, 10 Feb 2007 21:08:26 +0000

Bug Hunter:

Цитата 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;

}

Ку?

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

bizar — Fri, 09 Feb 2007 16:03:08 +0000

bizar:

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 ну ты мэн то что надо +++

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

Aloha — Tue, 06 Feb 2007 20:16:17 +0000

Aloha: 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

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

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

TheBug — Tue, 06 Feb 2007 17:47:49 +0000

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

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

Bug Hunter — Tue, 06 Feb 2007 16:19:21 +0000

Bug Hunter:

Цитата 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;

writeln;

end;

readln;

end.

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

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

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

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

procedure GetCombs(n: Word);

...

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

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

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

bizar — Mon, 05 Feb 2007 14:19:09 +0000

bizar:

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

#include
#include
#include
#include
#include

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< 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

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

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

Stratocoder — Mon, 05 Feb 2007 14:03:53 +0000

Stratocoder: - по сути массив, можно заменить
- ассоциативный массив, ставим в соответствие символу его индекс в массиве
- строки... это понятно
- ввод/вывод
- очередь

-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;

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

bizar — Mon, 05 Feb 2007 14:00:59 +0000

bizar: мне на php надо в ++ не селён для чего библиотеки . . . не знаю.

Добавлено 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 переделаю.

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

Stratocoder — Mon, 05 Feb 2007 13:41:10 +0000

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

#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++

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

MBo — Mon, 05 Feb 2007 13:40:46 +0000

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

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

MakedoneZ — Mon, 05 Feb 2007 13:31:04 +0000

MakedoneZ:

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;

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

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

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

bizar — Mon, 05 Feb 2007 13:21:08 +0000

bizar:

Цитата 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

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

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

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

esperanto — Mon, 05 Feb 2007 13:21:03 +0000

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

int main() {

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

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

Stratocoder — Mon, 05 Feb 2007 13:20:19 +0000

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

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

MIF — Mon, 05 Feb 2007 13:06:18 +0000

MIF:

Цитата 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). Однако, я ее забыл.

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

MakedoneZ — Mon, 05 Feb 2007 12:50:01 +0000

MakedoneZ:

for i := 0 to n-1 do

for j := i + 1 to n do

WriteLn(i,j);

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

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

bizar — Mon, 05 Feb 2007 12:45:54 +0000

bizar: Вот как в принципе выглядит но алгоритмом записать не могу придумать.
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

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.

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

MakedoneZ — Mon, 05 Feb 2007 12:43:58 +0000

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

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

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

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

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

1
2
3
12
13
23
123

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

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

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

bizar — Mon, 05 Feb 2007 12:35:41 +0000

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