2
$\begingroup$

I was thinking about an non-deterministic algorithm to generate all the subsets of the $\{1..n\}$ set.

Subsets(n)
    S' = null
    for i = 1..n    
        u = choice(1..n)
        if u in S'
           fail
        S' = S' + u
    for_each u in S'
         print u

How would I convert this algorithm into a deterministic form? I know that it is a lot more complicated to convert the choice statement in a deterministic manner but I want to get a general idea about maybe representing it in a deterministic manner.

$\endgroup$
1
$\begingroup$

Any finitely terminating non-deterministic algorithm can be made deterministic by using depth-first search on the tree of possible executions.

Or, to explain it another way: each time you have a non-deterministic choice, fork the program into multiple copies, one per possible choice. Forking might be done by calling the operating system's fork() call (very expensive), or by capturing all the relevant state of the variables and storing it in a set of pending items to explore (potentially tedious to write the code), or by replacing the choice() with a recursive call that makes a copy of all of the relevant state (i, S') and iteratively tries each of the possible choices (easiest to implement in this case).

Here is an example of how to implement the latter transformation. The state at the choice statement is the value of S' and i. So, we do the following:

search(S', i, u):
    if u in S'
        return
    S' = S' + u   # this needs to copy the set, not update it destructively
    i = i + 1
    if i>n:
        for_each u in S'
            print u
    else:
        for u in [1,2,..,n]
            search(S', i, u)

Subsets(n):
    for u in [1,2,..,n]:
        search(emptyset, 1, u)

Notice how search contains all of the code after the choice statement, until the next choice statement. We had to rip the for-loop over i apart to make this work, but the transformation was fairly mechanical.

This is a general method that can be used on any terminating non-deterministic algorithm -- not just this one.

$\endgroup$
  • $\begingroup$ Hello! Firstly, thank you for your explanation, secondly, so for each non deterministic algoritum i have to make a copy of the current state and change something to it at the next iteration? can you show me an example of the recursive call approach for this particular problem? $\endgroup$ – C. Cristi Dec 2 '19 at 7:39
  • 1
    $\begingroup$ @C.Cristi, I updated my answer with an example. $\endgroup$ – D.W. Dec 2 '19 at 11:19
  • 1
    $\begingroup$ Your opening sentence isn't true for trees that have infinite subtrees if your depth first ordering consistently chooses the infinite subtree. E.g. I might have a nondetermistic algorithm that outputs strings $1^*0$ that 50% of the time outputs 1 and recurses or just outputs 0. $\endgroup$ – orlp Dec 2 '19 at 13:16
  • 1
    $\begingroup$ @orlp, ooh, great point! I've edited accordingly. Thank you! $\endgroup$ – D.W. Dec 2 '19 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.