3 Replies - 543 Views - Last Post: 23 January 2018 - 01:35 PM Rate Topic: -----

#1 AstroBuzz   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 23-January 18

Recurrence question

Posted 23 January 2018 - 01:03 PM

Hi.
My method should pass n as argument and print/return all combinations of 0s and 1's but 1's should not stand next to each other.
eg.f(3) should return/print 000,001,100,010,101.
I would like to use recurrence. Is there anyone that knows how to do this?

Thanks in advance :)
Is This A Good Question/Topic? 0
  • +

Replies To: Recurrence question

#2 modi123_1   User is online

  • Suitor #2
  • member icon



Reputation: 15115
  • View blog
  • Posts: 60,492
  • Joined: 12-June 08

Re: Recurrence question

Posted 23 January 2018 - 01:08 PM

What have you tried, thought about, or considered?
Was This Post Helpful? 0
  • +
  • -

#3 AstroBuzz   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 23-January 18

Re: Recurrence question

Posted 23 January 2018 - 01:15 PM

View Postmodi123_1, on 23 January 2018 - 01:08 PM, said:

What have you tried, thought about, or considered?

I thought about something like this:
public static void zeros_ones(int n)
	{
		ArrayList<String> l = new ArrayList<String>();

		for (int i = 0; i < n; i++)
		{
			l.add("0");
		}

		for (int i = 0; i < n; i++)
		{
			l.set(i, "1");
			if (i>0)
			{
				l.set(i-1, "0");
				
			}
                        // here is the part where I would use recurrence.
			ArrayList<String> l2 = new ArrayList<String>(l);

			for (int j = i; j < n; ++j)
			{
				if (j>0 && l2.get(j-1).equals("1"))
				{
					continue;
				}else{
					l2.set(j, "1");
				}

				System.out.println(String.join("", l2));

			}

		}		
	}



I thought about concatenation of substring and execution of the method itself. eg return substring(0,i) + zeros_ones(n-1) but I'm not exactly sure what conditions should I use. Got some hint?
Was This Post Helpful? 0
  • +
  • -

#4 modi123_1   User is online

  • Suitor #2
  • member icon



Reputation: 15115
  • View blog
  • Posts: 60,492
  • Joined: 12-June 08

Re: Recurrence question

Posted 23 January 2018 - 01:35 PM

That's not pretty recursive. Perhaps starting with the larger problem - creating a series of strings that are permutations of 1's and 0's. (worry about the side by side bit later)

I would think the function would need an input string, the level, and the combined string.
First step would be to the check if this is level 0.. if it is exist the function since you don't want to go negative. Typically this is where I would append the 'combined string' for my checking)
Then start the work.. so decrement the level, and call the same function this time with the input string with addition to a 0.

Calling the same function is the recursion part!

When the function is returned because of hitting the level of 0 I want to it to call itself again but this time with the input string combined with '1'.

This way I should cover all the bases, right?

See if you can get it to generate all the permutations for 1 and 0.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1