Be seen. Boost your question’s priority for more expert views and faster solutions

we are offered two queues, 'q0' and 'q1'. a collection of numbers are input into these queues. the number one is given first followed by two etc(1,2,3,..n). input sequences can be permuted in different orders by executing the queue operations q0.enq, q1.enq, q0.deq, q1.deq, in a particular order. for example, the input sequence 1,2,3, can yield five different outputs:

output control sequence

1,2,3 q0.enq,q1.enq,q0.enq,q0.deq,q1.deq,q0.deq

1,3,2 q0.enq,q0.enq,q1.enq,q0.deq,q1.deq,q0.deq

2,1,3 q0.enq,q1.enq,q1.enq,q1.deq,q0.deq,q1.deq

2,3,1 q0.enq,q1.enq,q1.enq,q1.deq,q1.deq,q0.deq

3,1,2 q0.enq,q0.enq,q1.enq,q1.deq,q0.deq,q0.deq

3,2,1 not possible

not all permutations on n integers are possible as output, as 3,2,1 shows. how would i write an algorithm that determines if the desired output sequence is possible,and if so, which sequences leads up to it. To do this, we will attach two control numbers to the sequence, one number for the enqueues and one for the dequeues. Interpret an 'qo.enq' as a '0' and 'q1.enq' as a '1', so that the sequence of enqueues becomes a string of 0's and 1's, that can be interpreted as a binary number. for example

output enq-number deq-number

1,2,3 (010)=2 (010)=2

1,3,2 (001)=1 (101)=5

2,1,3 (011)=3 (101)=5

2,3,1 (011)=3 (110)=6

3,1,2 (001)=1 (100)=4

3,2,1 not possible

output control sequence

1,2,3 q0.enq,q1.enq,q0.enq,q0.de

1,3,2 q0.enq,q0.enq,q1.enq,q0.de

2,1,3 q0.enq,q1.enq,q1.enq,q1.de

2,3,1 q0.enq,q1.enq,q1.enq,q1.de

3,1,2 q0.enq,q0.enq,q1.enq,q1.de

3,2,1 not possible

not all permutations on n integers are possible as output, as 3,2,1 shows. how would i write an algorithm that determines if the desired output sequence is possible,and if so, which sequences leads up to it. To do this, we will attach two control numbers to the sequence, one number for the enqueues and one for the dequeues. Interpret an 'qo.enq' as a '0' and 'q1.enq' as a '1', so that the sequence of enqueues becomes a string of 0's and 1's, that can be interpreted as a binary number. for example

output enq-number deq-number

1,2,3 (010)=2 (010)=2

1,3,2 (001)=1 (101)=5

2,1,3 (011)=3 (101)=5

2,3,1 (011)=3 (110)=6

3,1,2 (001)=1 (100)=4

3,2,1 not possible

If you post some code and ask for help with problems, that would be fine.

Regards,

Mike.

sample input : "012" or "0231" or "2563014"

#include <vector>

#include <iostream>

#include <ostream>

#include <string>

#include <algorithm>

#include <functional>

using namespace std;

void main(void)

{

string s;

cout << "Input number : ";

cin >> s;

int count = s.length();

vector<int> map(count), prm(count); // prm - permutation

// convert string representation to int

for (int i = 0; i < count; i++)

map[s[i] - '0'] = prm[i] = i;

do

{

copy(prm.begin(), prm.end(), ostream_iterator<int>(cout

cout << " ";

string deq(count, '0'), enq(count, '0');

int deqInt = 0, enqInt = 0, q1pos = 0, q2pos = 0;

vector<bool> f(count, false);

for (int j = 0; j < count; j++)

{

int pos = map[prm[j]];

bool q1Posibility = find(f.begin() + q1pos, f.begin() + pos, false) != f.begin() + pos;

bool q2Posibility = find(f.begin() + q2pos, f.begin() + pos, false) != f.begin() + pos;

if (q1Posibility && q2Posibility && q2pos != 0)

{

cout << "not possible" << endl;

break;

} else

if (q1Posibility)

{

deq[j] = '1';

enq[pos] = '1';

deqInt |= 1 << j;

enqInt |= 1 << pos;

q2pos = pos + 1;

} else

q1pos = pos + 1;

f[pos] = true;

}

if (j >= count)

cout << "(" << enq << ") = " << enqInt << " ("<< deq << ") = " << deqInt << endl;

} while (next_permutation(prm.begi

}

Andrey

EE hasnot topic about algorithms...

it's really bad... computing is not only coding

Andrey

Moondancer

Community Support Moderator @ Experts Exchange

Home work --- sorting an array

but this algorithm is not trivial

Andrey

I will now reject the proposed answer, and will delete the question late in the day so partcipants can see the information provided here. Rather than answering what appears to be a homework question, PLEASE!:

-advise them that it is against policy

-tell them why you won't help and then stay out of it, or offer them only guidance and/or direction

-immediately post a Q at community support to report it so moderators can appropriately handle it.

Moondancer

Community Support Moderator @ Experts Exchange

I? iiieia??u ?oi ia?ia ae?i?eoi ?i?a?eaa?o. I?e??i ooo aiia?iyy ?aaioa? ou ?ai au ???i ??i ?a?eae.

A?? ia oai?e ?ia??oe...

A???e?u ao?ee

Warwar

MUDAK ty MOONDANCER

Kakya k chertu domashnyaya rabota. Narod algoritm ne znaet. Ty by ego hren zdelal!!!

Vse na tvoej sovesti

Derzhis' durik

Warwar

>>Home work --- sorting an array

Sorry Andrey_Kulik, but it doesn't matter how difficult or non-trivial the assignment. You can not do the homework.

If you want to help the questioner get to the answer, that's find, but you can not provide the answer.

You can assist.

IT'S ALGORIHTM

If you think that it's home work -- DO IT NOW

what do you know about algorithm's ?? Your programming experience == 0 if you don't know algorithm for a problem

warwar

>>If you think that it's home work -- DO IT NOW

I can not do it because it is homework.

I don't think you'r understanding me, so I'll let the moderator talk you through this.

Why you ?... You ignore my opinion :-/ is this really ok?

almost all question on EE -- home work or stupid questions.

I do ONLY algorithm questions because it's more hard then others

warwar

I do not understand the posting you made in another language, sorry.

Moondancer

Community Support Moderator @ Experts Exchange

a great deal of time working to get additional Topic-specific expert and Moderator to add insight on

this. With the thousands of questions to be handled, I'm doing this as quickly as I can. I will update

you as soon as I have a definitive response. I responded to this already earlier today and the comment

does not appear hear, so I'll add this again.

There are no "stupid" questions, since clearly people have a question and pay points to get help. The

line is drawn, though, when answers are given to homework questions, although guidance is OK. This

is all in the Member Agreement accepted by all who participate here, and the goal is to maintain "academic

honesty". Here is the link to the Agreement.

http://www.experts-exchange.com/jsp/infoMemberAgreement.jsp

Thanks for you patience, I will respond as quickly as I receive what is needed to further clarify the

specific issue here.

Moondancer

Community Support Moderator @ Experts Exchange

Almost all program products have set of algorithms in the source. if I write "Mathematica 5.0" and don't know some algorithm can i ask it ??

I also pay my points for this.

Andrey

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.

Could you help us resolve this issue? Please explain what you are using this algorithm for.

Some of the experts feel that it is a homework project. The general policy decided on by the community follows:

HOMEWORK

There has been several discussions among the experts about doing homework assignments. The general conclusion among the experts is to give guidance but not to actually do the homework for the person.

The purpose of homework is for you to learn and if an expert does it for you, you are not learning how to do it for yourself. Please keep this in mind when asking questions at the site. You are not really helping the student if you do their assignment for them. It's better to give guidance and help along the way but an important part of learning is actually doing the work yourself.

The experts are happy to help if you have problems but do not want to do the entire assignment for you.

We need your input to close this question.

Linda Gardner

Customer Service @ Experts Exchange