Zahlen, Stellen, Teilbarkeit

[CDW]

Also: gegeben sei eine Zahlenreihe von 0 bis n. Darin sollen alle Zahlen von 0 bis n vorkommen. Also eine Liste [0,1,2,3 ... n]
Nun kann man die Liste von der ersten Postion bis zur letzen durchgehen und daraus Zahlen bilden, in dem man einfach benachbarte Zahlen bis zur aktuellen Position zusammenstellt:
0
01 (eins)
012 (zwölf)
0123 (hundert dreiundzwanzig)

Schreibe ein Programm, welches die Zahlen nun so anordnet, dass in der Ergebnisliste eine bis zur i-ten Stelle zusammengesetzte Zahl in der Liste durch dieses i teilbar ist. Das i soll von 1 bis n+1 gehen - man soll also nacheinander immer größere Zahl bilden.

Bsp.:
0 bis 2: [0,1,2]
eine mögliche Lösung: [1,0,2]
Prüfung: i=1: 1 ist teilbar durch 1
i=2: 10 ist teilbar durch 2
i=3: 102 ist teilbar durch 3 = 34

weitere Lösung; 2,0,1
denn:
i=1: 2 ist teilbar durch 1
i=2: 20 ist teilbar durch 2
i=3: 201 teilbar durch 3

oder
0 bis 8: 0,1,2,3,4,5,6,7,8
[3,8,1,6,5,4,7,2,0]
Prüfung:
i=1: 3 teilbar durch 1
I=2: 38 teilbar durch 2
...
i=8: 38165472 teilbar durch 8 (=4770684)
i=9: 381654720 teilbar durch 9

gib eine Anordnung für 0,1,2,3,4,5,6,7,8,9 an

 

[dafil]

Spoiler: Zeige Lösung

Eine (die einzige) Lösung ist 3816547290

#include <iostream>
#include <set>

using namespace std;

void dostuff(int depth, int maxdepth, long long number, set<int> numbers_used)
{
    if (depth==maxdepth)
        cout << number << endl;
    else
        for (int i=0; i<maxdepth; i++)
            if ((number*10+i)%(depth+1)==0)
            {
                if (numbers_used.find(i)!=numbers_used.end())
                    continue;
                numbers_used.insert(i);
                dostuff(depth+1,maxdepth,number*10+i,numbers_used);
                numbers_used.erase(i);
            }
}

int main()
{
    set<int> numbers;
    dostuff(0,10,0,numbers);
    return 0;
}

 

[Ook!]

Python

from itertools import permutations

def valid(n, ps):
   seq = map(lambda i: int("".join(ps[:i])), range(1, n+2))
   return all(map(lambda i: seq[i-1] % i == 0 and seq[i-1] != 0, range(1, n+2)))

def itr(n):
   return filter(lambda ps: valid(n, ps), permutations(map(str, range(n+1))))

for ps in map(lambda ps: "".join(ps), itr(9)): print ps

Gruß
Felix