5 Replies Latest reply: Aug 16, 2009 5:53 AM by 800282 RSS

    Factoradic into k-subsets

    843853
      Hi,

      I've been trying to solve what I thought was a reasonably straight-forward Java problem - but to no success. I currently can't even determine an approach at this point...
      Here's my problem - is someone able to give me a hand?

      For a given array of points, I need to find all edges from point A to B, going through a maximum of N other points. This isn't too hard to begin with, but there are a number of constraints:

      The array needs to be a primitive array - i.e. int[]
      The process cannot be recursive.
      The process cannot modify the original array nor clone it...
      And the bit I'm really struggling with - for a given factoradic, I need to return the appropriate k-subset/permutation...

      An example...
      For the array {1,2,3,4,5}
      I want to get from 1 to 4 going through a maximum of 1 additional point
      The permutations are:
      {1->4}, {1->2->4},{1->3->4},{1->5->4}

      So I need something like:
      public static int[] getEdge(int[] points, int index)

      For the array above and an index of 2 (zero based) - I would like to get {1,3,4}

      Regards
      Col.
        • 1. Re: Factoradic into k-subsets
          800282
          The process cannot be recursive.
          Why?
          The process cannot modify the original array nor clone it...
          That sounds like a strange requirement. Why can't you create a copy of the array to work with?
          And the bit I'm really struggling with - for a given factoradic, I need to return the appropriate k-subset/permutation...
          Please define "appropriate".
          An example...
          For the array {1,2,3,4,5}
          I want to get from 1 to 4 going through a maximum of 1 additional point
          The permutations are:
          {1->4}, {1->2->4},{1->3->4},{1->5->4}

          So I need something like:
          public static int[] getEdge(int[] points, int index)

          For the array above and an index of 2 (zero based) - I would like to get {1,3,4}
          Why not {1,2,4} or {1,5,4}? Why is {1,3,4} the "appropriate" subset?

          By the fact you have (IMO) some strange requirements, I get the impression that this is homework. Correct? If not, could you tell what "real world" problem you're trying to solve? Chances are that you have your mind set on this specific solution while there may very well be a better one. Explaining what you're trying to solve may lead to some new idea.
          • 2. Re: Factoradic into k-subsets
            843853
            Thought someone would take exception to the requirements....
            Generally these requirements come from the fact this code will be written in both Java and C and used for some example workshops I'm running. I wish to get the algo sorted in Java first as I am more comfortable porting from Java to C than the other way around. The algorithm will be executed by many threads simultaneously, working with 'work packages'. Hence the need to evaluate a single item in isolation.

            a) Non-recursive - the device the C code will run on doesn't allow for recursive functions, and I want the algo to be similar for this demo - a recursive Java-only, single threaded version would be trivial.

            b) Cloning the array - I'd prefer not to - as it's likely to be quite big - and the algorithm will be called a lot of times in a highly parallel fashion - thus, there would be many, many clones of it. If I was to run many threads concurrently I would likely run out of RAM.

            c) For the array above and an index of 2 (zero based) - I would like to get {1,3,4}
            Obviously this needs clarification. An index of 0 would return {1,4}, 1 would return {1,2,4} and 3 would return {1,5,4}. i.e. Work package 0,1,2,3...etc

            d) I get the impression that this is homework.... Lol... I'm currently at home and working - so in a way you're correct. However, if you believe this is some assignment set by an educational institute - then rest assured - no uni I've ever attended would set something this bizarre upon it's students.

            Col.

            Edited by: colinfindlay on 14/08/2009 22:34
            • 3. Re: Factoradic into k-subsets
              800282
              Thanks for the additional info.
              colinfindlay wrote:
              c) For the array above and an index of 2 (zero based) - I would like to get {1,3,4}
              Obviously this needs clarification. An index of 0 would return {1,4}, 1 would return {1,2,4} and 3 would return {1,5,4}. i.e. Work package 0,1,2,3...etc
              It's still not entirely clear to me what you want. In your original post you mentioned you wanted to get a single value (number of int's) back from a method. Then why enumerate over all possible combinations/permutations? Given the set {1,2,3,4,5} and from=1 and to=4 with maximum path length of 2, surely there is no need to iterate? Can you explain in more detail perhaps? Even provide some more example(s) (larger set and path)?
              • 4. Re: Factoradic into k-subsets
                843853
                I don't remember ever mentioning iterating over the subset....I only mentioned no recursion?
                Although I didn't want to influence approach - here's some code that does something vaguely similar, but produces combinations rather than permutations...It also only works for a single array of a single size. (I could call this however from something that generated the appropriate k-subset)
                     public static String factoradic(String[] s,long l, double power) 
                
                    { 
                     StringBuilder sb = new StringBuilder();
                        while (power >= 0) 
                        { 
                            sb = sb.append(s[(int)(l % s.length)]); 
                            sb.append(',');
                            l /= s.length; 
                            power--; 
                        } 
                        return sb.toString(); 
                    }
                • 5. Re: Factoradic into k-subsets
                  800282
                  colinfindlay wrote:
                  I don't remember ever mentioning iterating over the subset....
                  You're right. I'd even go as far as saying you mentioned very little: you still didn't answer all my questions. What is "most appropriate"? And you also didn't post some more examples so I could extract this information from the examples rather than your explanation.
                  Never mind though, perhaps it's just me and is someone else able to give you a hand based on the information provided thus far.

                  Good luck.