Results 1 to 9 of 9
  1. #1
    MitchellWall is offline Member
    Join Date
    Nov 2013
    Posts
    3
    Rep Power
    0

    Default Joesphus Problem

    I'm trying to work with the Josephus Problem of continually removing an element until one remains through a circular Linked List. I am lost of how to remove the element though. I keep getting NullPointerExceptions and I do not know why.

    For my version of the Josephus, I use int elements
    such as

    1 2 3 4 5 6
    and let's remove every second element until 1 remains
    4 5 6 1 2
    1 2 4 5
    5 1 2
    5 1
    1
    element 1 is the remainder.

    I am able to add all elements, but removing is the difficulty.
    Java Code:
    /**
    * Prisoner is a class that is used for a linked list
    * of prisoners.  The linked list is
    * circular where the tail points back to the head.
    */
    //import java.util.Iterator;
    class Prisoner{ 
        
        class DigitNode
        {
                public int num=0;			// Digit's position in line
                public DigitNode next=null;	// Reference to next Digit
                /**
                * Digit constructor, initializes number
                */
    
                public DigitNode(int number)
                {
                       //
                    num = number;
                    next = null;
                }
                
                public String toString() {
                    return "" + num;
                }
    
        }
        
        private int digit;
        private DigitNode head = null;	// Linked list of prisoners
        private DigitNode tail = null;	// Tracks end of list as it is constructed
        
        /**
         * constructs a circular linked list of
         * @param n DigitNode, current is the first DigitNode and tail is the last DigitNode(next of tail is current)
         */
       
        public Digi(int n)
        {
            //
            digit= n;
            head = null;
            tail = null;
         }
        
        public void add(int n) {
            DigitNode newNode = new DigitNode(n);
            newNode.next = head;
            head = newNode;
        }
        
        /*
         * prints all Digit starting from current until tail
         */
        @Override
         public String toString()
         {
    	//
             String strVal = "";
             Digit p = new Digit(digit);
             
             for (int i = digit; i >= 1; i--) {
                 p.add(i);
             }
             DigitNode position = p.head;
             while (position != null) {
                 strVal = strVal + position.num + " ";
                 //System.out.println(strVal);
                 position = position.next;
             }
             return strVal;
         }
               
         /**
          * moves the current 
          * @param n positions
          */
         public void move(int k)
         {
         	//
             DigitNode current = head;
             while (current.num != k) {
                 current = current.next;
             }
         }
         /*
          * call move(k) and then remove the digit in current position
          */
         public void eliminate(int k)
         {
            //  
             
             move(k);
             DigitNode current = head;
             DigitNode previous = tail;
             
             while (current.num != k) {
                 previous = current;
                 current = current.next;
             }
             if ( current == head) {
                 head = head.next;
             } else {
                 previous.next = current.next;
             }
    
         }
         
              
    }
    Last edited by MitchellWall; 11-20-2013 at 10:04 PM. Reason: added [code] ... [/code] tags

  2. #2
    MitchellWall is offline Member
    Join Date
    Nov 2013
    Posts
    3
    Rep Power
    0

    Default Re: Joesphus Problem

    Thank you for adding code tags, now I know how to do that JosAH.

  3. #3
    MitchellWall is offline Member
    Join Date
    Nov 2013
    Posts
    3
    Rep Power
    0

    Default Joesphus Problem

    I'm trying to work with the Josephus Problem of continually removing an element until one remains through a circular Linked List. I am lost of how to remove the element though. I keep getting NullPointerExceptions and I do not know why.

    For my version of the Josephus, I use int elements
    such as

    1 2 3 4 5 6
    and let's remove every second element until 1 remains
    4 5 6 1 2
    1 2 4 5
    5 1 2
    5 1
    1
    element 1 is the remainder.

    I am able to add all elements, but removing is the difficulty.
    Java Code:
    /**
    * Prisoner is a class that is used for a linked list
    * of prisoners.  The linked list is
    * circular where the tail points back to the head.
    */
    //import java.util.Iterator;
    class Prisoner{ 
        
        class DigitNode
        {
                public int num=0;			// Digit's position in line
                public DigitNode next=null;	// Reference to next Digit
                /**
                * Digit constructor, initializes number
                */
    
                public DigitNode(int number)
                {
                       //
                    num = number;
                    next = null;
                }
                
                public String toString() {
                    return "" + num;
                }
    
        }
        
        private int digit;
        private DigitNode head = null;	// Linked list of prisoners
        private DigitNode tail = null;	// Tracks end of list as it is constructed
        
        /**
         * constructs a circular linked list of
         * @param n DigitNode, current is the first DigitNode and tail is the last DigitNode(next of tail is current)
         */
       
        public Digi(int n)
        {
            //
            digit= n;
            head = null;
            tail = null;
         }
        
        public void add(int n) {
            DigitNode newNode = new DigitNode(n);
            newNode.next = head;
            head = newNode;
        }
        
        /*
         * prints all Digit starting from current until tail
         */
        @Override
         public String toString()
         {
    	//
             String strVal = "";
             Digit p = new Digit(digit);
             
             for (int i = digit; i >= 1; i--) {
                 p.add(i);
             }
             DigitNode position = p.head;
             while (position != null) {
                 strVal = strVal + position.num + " ";
                 //System.out.println(strVal);
                 position = position.next;
             }
             return strVal;
         }
               
         /**
          * moves the current 
          * @param n positions
          */
         public void move(int k)
         {
         	//
             DigitNode current = head;
             while (current.num != k) {
                 current = current.next;
             }
         }
         /*
          * call move(k) and then remove the digit in current position
          */
         public void eliminate(int k)
         {
            //  
             
             move(k);
             DigitNode current = head;
             DigitNode previous = tail;
             
             while (current.num != k) {
                 previous = current;
                 current = current.next;
             }
             if ( current == head) {
                 head = head.next;
             } else {
                 previous.next = current.next;
             }
    
         }
         
              
    }

  4. #4
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,510
    Rep Power
    5

    Default Re: Joesphus Problem

    I am assuming you mean removing an item in a linked list.

    In a circular linked list, the tail points back to the head. So to delete an item, save the parent of the item you want to delete. Now you have parentOfItem so you just need to have parentOfItem.child = item.child. And the link is deleted. When item.child = item, the node points to itself, so you are done since you only have one item remaining.

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  5. #5
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,436
    Blog Entries
    7
    Rep Power
    20

    Default Re: Joesphus Problem

    If I remove every second element from the circular list (1, 2, 3, 4, 5, 6) I get (1, 3, 5); I don't understand your result ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  6. #6
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,436
    Blog Entries
    7
    Rep Power
    20

    Default Re: Joesphus Problem

    What happened to this thread? There's a 'soft link', pointing to the same thread; one of the links states that the thread was moved ... it's bitrot, I'm telling you ...

    kind regards,

    Jos

    ps. I don't dare to remove one of the 'links'.
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    3,876
    Rep Power
    5

    Default Re: Joesphus Problem

    ... I have no idea what you're talking about here! I see nothing wrong.
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

  8. #8
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,436
    Blog Entries
    7
    Rep Power
    20

    Default Re: Joesphus Problem

    Don't you see two (identical) threads 'Josephus Problem' and one of them seems to be moved; they're both one thread only ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  9. #9
    natdizzle's Avatar
    natdizzle is offline Nathan Nelson
    Join Date
    Jan 2009
    Posts
    100
    Rep Power
    0

    Default Re: Joesphus Problem

    i use arraylists remove method.. and make sure you have the right index

    im removing from a list here Lists

    its also supposed to be a countdown too zero

Similar Threads

  1. Problem with a Simple Histogram Problem
    By kathmandu in forum New To Java
    Replies: 12
    Last Post: 06-25-2013, 01:19 AM
  2. Replies: 0
    Last Post: 11-07-2012, 12:44 PM
  3. Small problem with problem with Java, C++ parse program.
    By dragstang86 in forum New To Java
    Replies: 4
    Last Post: 10-30-2011, 03:43 AM
  4. Replies: 9
    Last Post: 09-21-2010, 04:15 PM
  5. simple line problem / for loop problem
    By helpisontheway in forum New To Java
    Replies: 1
    Last Post: 11-17-2009, 06:12 AM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •