Solved

Refactor procedural algorithm to OOP

Posted on 2016-09-08
3
77 Views
Last Modified: 2016-09-12
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;
                }
            }
        }
    }
}

Open in new window

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
}

Open in new window

And I want to transform this so I can call it via:
p = new algorithm()

while(p.hasnext())
    A = p.next()
endwhile

Open in new window

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>());
        }
    
    }

Open in new window

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

Open in new window

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.)
0
Comment
Question by:deleyd
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
3 Comments
 
LVL 34

Accepted Solution

by:
sarabande earned 167 total points
ID: 41790824
where I can call hasnext() and next() to get the next permutation

using of hasnext or next doesn't turn it from procedural code to OOP.

a while loop used by an outer object to control action on a lower object (here your list) is an evidance for procedural code. for OOP you would need to create a class that is derived from the list or owns the list and where you can get the whole list of permutations and the count and perhaps each single permutation by index. true OOP you would get by creating an iterator class which gets initialized by using begin member function of your permuter class and ends by checking whether next iteration meets the end member function. for iteration you should overload the ++ operator (or next member function if you like better).

Sara
0
 
LVL 11

Assisted Solution

by:louisfr
louisfr earned 166 total points
ID: 41790836
You could use an iterator:
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");
            foreach(List<string> L in generate(list))
                output(L);
        }

        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 IEnumerate<<List<string>> 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;
            }

            yield return A;

            for (int i = 0; i < n; )
            {
                if (c[i] < i)
                {
                    if (IsEven(i))
                    {
                        swap(A, 0, i);
                    }
                    else
                    {
                        swap(A, c[i], i);
                    }
                    yield return A;
                    c[i] += 1;
                    i = 0;
                }
                else
                {
                    c[i] = 0;
                    i += 1;
                }
            }
        }
    }
}

Open in new window

0
 
LVL 33

Assisted Solution

by:ste5an
ste5an earned 167 total points
ID: 41790841
OOP is imho not the exact term. Cause you want a special behavior called iterator pattern.  And much better: .NET has the IEnumerable pattern and even the yield keyword.

For your concrete problems:

return (new List<String>()): you need to accept a set as input and you need to generate a set as output. Thus it is basically ok. But you should later one thing about using more abstract classes or interfaces here.
Also there is imho no need for a specific data type, so you should use generics.

hasnext(): permutations are a fixed number of elements over a given start set. Thus you can calculate his number once at the beginning and use a simple counter for hasnext(). But the drawback: It is n! (faculty), thus this can lead quickly to an overflow. So you need to simply use a cache approach. Create one permutation in advance and return it later. When this is possible, then you have the answer for hasnext(). Thus you need to create one in the constructor to initialize it,

So I would use a class like

    public class Permutations<T> : IEnumerable<T>
    {
        public Permutations(IList<T> set)
        {
        }
    }

Open in new window

1

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction Although it is an old technology, serial ports are still being used by many hardware manufacturers. If you develop applications in C#, Microsoft .NET framework has SerialPort class to communicate with the serial ports.  I needed to…
It was really hard time for me to get the understanding of Delegates in C#. I went through many websites and articles but I found them very clumsy. After going through those sites, I noted down the points in a easy way so here I am sharing that unde…
In a recent question (https://www.experts-exchange.com/questions/29004105/Run-AutoHotkey-script-directly-from-Notepad.html) here at Experts Exchange, a member asked how to run an AutoHotkey script (.AHK) directly from Notepad++ (aka NPP). This video…

763 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question