Восстановление исходного массива

[IgorGO]

присоединяюсь. интересно как решилось.
попробовал "поиск решений" получил дырку от бублика. из алгоритмов в голове перебор вариантов в лоб. количество только круто растет. массив из N элементов это N! вариантов. для 4 это 24, а для 10 это уже 3.6 млн. штук.

[Tronix]

Нашел кросс-пост от автора здесь: http://www.cyberforum.ru/algorithms/thread193287.html
Там же предлагают вариант на Си (эээ ++ наверно). Пока не пробовал (компилить не чем) и не знаю, работает ли. В любом случае буду следить за этой и той темой. Посмотрим что автор скажет.

UPD: Скомпилил тот пример на C++, работает на малых примерах вроде нормально. Хмм, будем разбираться...

[кот Бегемот]

Всё оказалось очень гениально просто. Не нужен ни перебор, ни рекурсия, ни функции, ни процедуры.
Изящное решение предложил Сергей (ms@samaralan.ru)
За что ему мой респект и уважуха.

[Serge_Bliznykov]

>>Изящное решение предложил Сергей (ms@samaralan.ru)
так что за решение? секрет, ноу-хау? Или поделитесь?...

[IgorGO]

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

итак вот такой конечный массив А(А(i))
2 3 8 7 4 5 6 1
а вот, оказывается, с каких исходных массивов он может быть получен A(i):
4 7 6 2 1 8 3 5
5 4 7 3 2 1 8 6
6 5 4 8 3 2 1 7
7 6 5 1 8 3 2 4

[кот Бегемот]

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

Итак, общая задача:
Массив А состоит из неповторяющихся чисел от 1 до N
Массив B сформирован из массива А по закону: B[A[A[i]]]=i
По данному массиву В найти массив А

for i := 0 to n - 1 do begin
k := Src[i];
k := Src[Pred(k)];
Dst[Pred(k)] := Succ(i);
end;

[IgorGO]

кот Бегемот,
удалось ли по массиву B(i) = A(A(i)) = 2 3 8 7 4 5 6 1
получить 4-е возможных варианта масиива А?
4 7 6 2 1 8 3 5
5 4 7 3 2 1 8 6
6 5 4 8 3 2 1 7
7 6 5 1 8 3 2 4

ясен-красен, что я тоже решал общую задачу для массива из N элементов. Выглядит это так:

Dim C As Long, F As Long, i() As Long, r()

Function FindInitArray(rg As Range)
Dim a As Long
C = rg.Cells.Count
ReDim r(1 To C)
ReDim i(1 To 10, 1 To C)
F = 1
a = 1
For Each cl In rg.Cells
r(a) = cl.Value
a = a + 1
Next
NextV (1)
For a = 1 To C
If i(1, i(1, a)) <> r(a) Then FindInitArray = "Nothing": Exit Function
Next
FindInitArray = i
End Function

в данном коде не приведена только рекурсивная процедура NextV, которая собственно и перебирает варианты и складывает их в i(a,b). сначала я перебирал варианты в одномерном массиве i(a), останавливая NextV на первом удачном, а когда понял, что решений может быть не одно - стал собирать варианты в i(a,b).

[кот Бегемот]

Что вы все читать что ли не умеете? В задании (повторяю в третий раз) необходимо найти любой вариант, а вовсе не все возможные.