troubleshooting Question

Refactor procedural algorithm to OOP

Avatar of deleyd
deleydFlag for United States of America asked on
C#
3 Comments3 Solutions212 ViewsLast Modified:
I'm looking at an algorithm for generating permutations, and I notice it has an "output" statement buried deep in the main loop.

What I'd like is an OOP way of doing this, where I can call hasnext() and next() to get the next permutation, and then do what I like with it. That way I'm in control, rather than the algorithm being in control saying, "Here's the next permutation, and the next, and the next..."

My specific example is Heap's algorithm for generating permutations:
https://en.wikipedia.org/wiki/Heap's_algorithm

I don't like how it has an "output" statement nested deep within the main loop. That seems like an old fashioned procedural way of doing things.

Is there a general method for converting procedural algorithms to OOP? I'm using this permutation algorithm as a concrete example. I'm hoping if I can convert this specific example, then I'll see the general pattern.

Here's a working C# program:

using System;
using System.Collections.Generic;
using System.Text;

namespace permute1
{
    class Program
    {
        static void Main(string[] args)
        {
            List<String> list = new List<String>();
            list.Add("A");
            list.Add("B");
            list.Add("C");
            generate(list);
        }

        public static void output(List<String> A)
        {
            foreach (String s in A)
            {
                System.Console.Write(s);
            }
            System.Console.WriteLine("");
        }

        public static bool IsEven(int value)
        {
            return value % 2 == 0;
        }

        public static void swap(List<String> A, int position1, int position2)
        {
            String temp = A[position1]; // Copy the first position's element
            A[position1] = A[position2]; // Assign to the second element
            A[position2] = temp; // Assign to the first element
        }

        public static void generate(List<String> A)
        {
            //HEAP'S ALGORITHM FOR GENERATING PERMUTATIONS
            int n = A.Count;

            int[] c = new int[n];

            for (int i = 0; i < n; i++)
            {
                c[i] = 0;
            }

            output(A);

            for (int i = 0; i < n; )
            {
                if (c[i] < i)
                {
                    if (IsEven(i))
                    {
                        swap(A, 0, i);
                    }
                    else
                    {
                        swap(A, c[i], i);
                    }
                    output(A);
                    c[i] += 1;
                    i = 0;
                }
                else
                {
                    c[i] = 0;
                    i += 1;
                }
            }
        }
    }
}
In general I have code such as:
method algorithm()
{
    initializing code
    .
    .
    output(A);

    while(condition)
        if (something)
            code
            .
            .
            output(A);

            more code
            .
            .
        else
            other code
            .
            .
    endwhile
}
And I want to transform this so I can call it via:
p = new algorithm()

while(p.hasnext())
    A = p.next()
endwhile
This means my next() method should somehow jump back into the middle of the while loop after the output(A) statement at the "more code" spot, which isn't easy (or is impossible).

I came up with this class which almost does what I want. The class holds state variables which keep track of where we are in the algorithm. The state variables are initialized in the Constructor.
    class permuter
    {
        List<String> A;
        int[] c;
        int n;
        int i;

        public permuter(List<String> I)
        {
            this.A = new List<String>(I);
            this.n = A.Count;
            this.c = new int[n];

            for (int j = 0; j < n; j++)
            {
                c[j] = 0;
            }
        }

        public bool hasnext()
        {
            return (this.i < this.n);
        }

        public bool IsEven(int value)
        {
            return value % 2 == 0;
        }

        public void swap(List<String> A, int position1, int position2)
        {
            String temp = A[position1]; // Copy the first position's element
            A[position1] = A[position2]; // Assign to the second element
            A[position2] = temp; // Assign to the first element
        }

        public List<String> next()
        {
            while (i < n)
            {
                if (c[i] < i)
                {
                    if (IsEven(i))
                    {
                        swap(A, 0, i);
                    }
                    else
                    {
                        swap(A, c[i], i);
                    }
                    c[i] += 1;
                    i = 0;
                    return (A);
                }
                else
                {
                    c[i] = 0;
                    i += 1;
                }
            }
            return (new List<String>());
        }
    
    }
It's not perfect.
I had to add a return (new List<String>()); to the end of the next() method, so all paths return a List.

Problem: On the last iteration, p.hasnext() says there's a next element when actually there isn't, and the method executes return (new List<String>()); returning an empty List, which isn't satisfying.

hasnext() actually doesn't know if there's a next element, because we haven't generated it yet. At the same time, I don't want the hasnext() method to generate the next element, because I can't count on the caller always calling hasnext() before calling next().

I could throw in a whole boatload of flags:
"have we run the initializing code?"
"have we generated the next permutation?"
"have we returned the next permutation?"
The code quickly becomes messy with a bunch of if statements.

i also considered running the algorithm in a separate thread, where it generates a permutation, places it somewhere to be fetched, then pauses within the loop and waits for a resume signal. Sounds messy.

Code to call the above class:
        static void Main(string[] args)
        {
            List<String> list = new List<String>();
            list.Add("A");
            list.Add("B");
            list.Add("C");
            permuter p = new permuter(list);
            output(list);
            while (p.hasnext())
            {
                List<String> L = p.next();
                output(L);
            }
        }
Is there a general method for handling these situations?

(Sometimes I encounter procedural code that I want to convert to OOP. For example, awhile ago I encountered some procedural code that had a Read Input() statement followed by more code handling the input. I couldn't run this in a GUI because the Read statement blocked the message pump, preventing the Read from happening. I had to queue up the Read, then provide a separate callback method to handle the read. The separate callback method had to know which read it was handling.)
SOLUTION
ste5an
Senior Developer

Our community of experts have been thoroughly vetted for their expertise and industry experience.

Join our community to see this answer!
Unlock 3 Answers and 3 Comments.
Start Free Trial
Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.
Unlock 3 Answers and 3 Comments.
Try for 7 days

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.

-Mike Kapnisakis, Warner Bros