Swap 2 values of 2 variables without using a third variable; python

Question

So, a friend of mine asked how my python programming was coming; I said I was learning a lot and that it was coming along nicely. Then my friend, a math-snob, asks me:

"Can you swap the value of 2 variables without using a third variable as a temporary placeholder?"

Solution 1

The canonical way to swap two variables in Python is

a, b = b, a

Please note than this is valid whatever the "type" of a or b is (numeric, string, tuple, object, ...). Of course, it works too if both variables reference values of different types.

---

As many imperative languages, Python evaluates assignments right to left. Conceptually all behave like if a tuple was build for the right hand part of the expression, and then deconstructed to perform the affectation to the left hand part. This has already been explained more clearly than I can here: https://stackoverflow.com/a/14836456/2363712

The real details are implementation dependent though. For example, to build on a comment by @undefined is not a function below, the CPython virtual machine has a ROT_TWO opcode that swap the two top-level items on the stack, and so allow to optimize such affectation. See this previous answer for a detailed explanation: https://stackoverflow.com/a/21047622/2363712

Solution 2

This is the main snippet of code:

 x = x + y;  // x now becomes 15
 y = x - y;  // y becomes 10
 x = x - y;  // x becomes 5

This is what you friend meant.

Solution 3

If your friend is a "math-snob", he may have in mind a particular trick, which you can use in languages where you can apply the XOR function to the bitstring representation of numbers.

Say we have variables X and Y, with starting values of a and b respectively. Perform the following assignments (the values of the variables which result are shown as comments):

(start)      # X == a; Y == b
X = X XOR Y  # X == a XOR b;  Y == b
Y = X XOR Y  # X == a XOR b;  Y == b XOR (a XOR b)
X = X XOR Y  # X == (a XOR b) XOR b XOR (a XOR b);  Y == b XOR (a XOR b)

Because XOR is associative, we can regroup the resulting equations as follows:

X == (a XOR a) XOR (b XOR b) XOR b
Y == (b XOR b) XOR a

Because x XOR x == 0 and x XOR 0 == x, we can simply remove all those pairs of variables XOR'ed with themselves, and what's left is:

X == b
Y == a

which is what we wanted, to switch the values without using a third variable.

It's been quite a while since I did any bit manipulation in Python, so I cannot tell you whether this trick works in Python, but there are languages where it works. I also can't tell you whether it actually has sufficient benefits to balance out its non-obviousness.

Solution 4

You can directly try for:

a, b = b, a

It is a canonical way to exchange the value without using a third variable.

View more solutions

Comments

[TheSoundDefense]

But this would only work on numeric variables, correct?

[Sylvain Leroux]

Could you explain why left, right = right, left is considered a "bad answer"? As I understand, the question is "Python oriented" -- so why not use the language idioms to solve problems.

[murgatroid99]

Honestly, the first method you posted is a terrible way of implementing swap in Python. It will fail silently on many floating point values, and it won't work at all for non-numeric types.

[TheSoundDefense]

I'm not sure why you would want a more "portable" way of doing this, to be honest. It's not like people copy Python code, paste it into a .c file, and make a few adjustments. If all you're doing is swapping numbers, I don't know if it's worth the effort for such a low-level operation.

[Brendan]

Internally this may use an extra location on the stack though. There is a way to get Python's bytecode(?) instructions to find this out but I don't know this off the top of my head ...

[Sylvain Leroux]

@Brendan Implementation detail? ;) More seriously, you probably have right. But as I understand the question this is really without using a third Python variable, not "an intermediate memory location".

[Ashwini Chaudhary]

A tuple is not created when we swap just 2 variables, instead ROT_TWO is used.

[Sylvain Leroux]

@undefinedisnotafunction Thank you for the pointer! I will edit my answer the best I can to reflect than.

[Ashwini Chaudhary]

I think you should probably replace the link in your answer with this great answer from Martijn.

[Sylvain Leroux]

@undefinedisnotafunction Thank you again. Finally, I keep them both, as Martijn's answer is great concerning the CPython implementation, whereas the previous one has the virtue of simplicity. Even if that later is not "correct" from an implementation point of view, I think it provides a representation "right enough" to be understandable by most Python newcomers. Or am I wrong?

[todd_dsm]

@SylvainLeroux: the 'left, right = right, left' explanation is below the program.

[todd_dsm]

@TheSoundDefense I tested after changing from integers to strings, the output still swaps values.

[todd_dsm]

@murgatroid99: TRUE. While the code would require normalization to a type of either 'int' or 'float' the logic still holds.

[todd_dsm]

@TheSoundDefense: portability is a small but important step. Like running a 10k marathon and stopping a 100 yards before the finish line. The program is the hard work; portability is the last few steps. And generally, it's the thing that makes you look like a more thoughtful programmer during an interview; if you're not thinking about it, the other candidate is.

[TheSoundDefense]

@todd_dsm if it's only one or two lines of code, and it's risky and suboptimal in both languages, then I would not be that worried about portability. When I think portability concerns, I think things like "will these signals work correctly on Windows?" not "how can I change this variable swap to C while changing as few characters as possible?"

[user2357112]

"As many imperative languages, Python evaluate right to left" - no, it's almost always left to right. Assignment is just a weird special case.

[murgatroid99]

@todd_dsm You can't normalize a list or a dict to a number. And this won't work for most floats either, because of how floating point numbers work. There is no reason to write code that can be translated almost character by character to another language instead of writing code that works well in the language you're working in.

[todd_dsm]

I don't mind the peer-review but I've been good enough to show my work. If you're going to vote me down then demonstrate a better method by showing your work. That will take us from opinion to fact; the alternative is a little lazy.

[todd_dsm]

@TheSoundDefense: yes - both are portability questions. Also when you start using words like 'risky' it makes me think more testing is required. Fully-tested code poses greatly, if not fully, mitigated risk.

[todd_dsm]

@murgatroid99: the issue you raised was first about types 'int' and 'float', now you want to extend that to lists and dictionaries? Try to keep your comments within the context of the problem.

[murgatroid99]

@todd_dsm The context of the problem? Your question never mentions any types at all. It says "variables". Your solution is the only thing constraining the problem. If you pass two variables of any type into the first solution, it works as expected. The second function will succeed if the variables are integers, give incorrect results for floating point numbers and some objects with custom operators, and throw an error for all other objects. It doesn't even work within your weird assumptions. It doesn't even technically work in C, where overflow is technically undefined.

[todd_dsm]

@murgatroid99: The only weird assumption was swapping integers and strings - not so weird when you think about it; happens to work nicely. It's not a fix-all for every problem you can imagine; it won't do your dishes, remove lipstick for your collar or pay your taxes. Say something useful or zip it. Show your work.

[todd_dsm]

@murgatroid99 Tested it with with both positive and negative floats - it still holds. I'm not sure what you're talking about.

[murgatroid99]

You yourself said that you wanted to swap floating point numbers, but your solution doesn't even do that properly. For example, arguments 0.0000001 and 1000000 gives incorrect output. And I'm not really sure why you mentioned strings; it definitely doesn't work with them (they don't have a subtraction operator defined).

[todd_dsm]

@murgatroid99 1) Floats: what your seeing is exponent notation because a byte-count word boundary was crossed but - it breaks in the solution you prefer as well. So, convert the numbers then change the '%r's to '%f's; in vim: %s/%r/%f/g; solved. 2) I said nothing of strings, that was in response to the first comment (TheSoundDefense); test results show strings being swapped as well.

[murgatroid99]

You don't understand. The output from the input I gave is (1000000.0, 1.00000761449337e-07). That's not just the exponent output, there's a different number before the e. How about this: try 0.3 and 1.0. That results in (1.0, 0.30000000000000004). That's a different number.

[murgatroid99]

The fundamental problem here is that you are trying to replace built in functionality for swapping variables for code that works with fewer inputs, has unexpected outputs on some inputs, can have unexpected side effects, and isn't even more portable. The C version of this code depends on compiler behavior for integer values and will output the wrong values for floating point inputs for the same reason. There is absolutely no reason to ever use that function in Python code, and putting it in a library will only cause your API consumers to make incorrect assumptions about its behavior.

[todd_dsm]

@murgatroid99 1) I'm not sure what you're doing different; given your values I get: values: 'x' is 0.300000 and 'y' is 1.000000 for output; long but correct. 2) This is a learning exorcise, not an API.

[murgatroid99]

I'm running your code as written in a Python 2.7 prompt. And that doesn't matter. The output for the first input I suggested is still wrong. And if you don't understand how 0.000000100000761449337 is different from 0.0000001, I can't help you.

[murgatroid99]

OK, it's a learning exercise. You asked how to do something in Python. You proposed a solution. Several people, including me, explained the problems with your solution. Your comments indicate that you have failed to learn anything.

[todd_dsm]

@murgatroid99 I can see that you're getting a different value - I just don't know how; 'I'm running it in the command line' does not explain what you are doing; there's no way to do that. Are you in/using the interpreter? IDLE? When I run it - it works; drop it in a script and execute: $ python swap2vars.py

[todd_dsm]

@murgatroid99 THE PROBLEM YOU POSED BREAKS IN BOTH SCENARIOS (mine and the other one). YOU STILL HAVE TO CONVERT THE NUMBERS. You broke a word boundary - good for you: CONVERT THE NUMBERS.

[murgatroid99]

OK, your interpreter seems to be displaying values more rounded than mine is. Try the inputs 1e10 and 1e-10. I get the output (0.0, 10000000000.0)

[todd_dsm]

@murgatroid99 Given your latest input, I get the same output as you. The answer doesn't change though. The floats must be converted in either case.

[murgatroid99]

If by either case, you mean either of the functions you wrote, then you are wrong. swapNosC does no conversions at all, and works for literally any pair of Python values.

[todd_dsm]

@murgatroid99 Testing your inputs with both functions produces exactly the same result for me. You may have some esoteric environmental condition set - or I do. But I can't imagine what it might be. Further, this is a failure of python static semantics. In this case Python should display a meaningful error like it does everywhere else. Instead it rounds in a predictable but potentially unwanted manner. No language should automatically be making any decision for you but rather error so you can work around the inadequacy. The function is independent of this issue.

[murgatroid99]

The behavior you are describing is the inherent behavior of floating point numbers. It's not python specific or specific to my machine. It's not a decision, and it's not an error. And I have no idea what the hell you're testing, but if I run swapNosC(1e10, 1e-10), the output is (1e-10, 10000000000.0). The syntax a,b = b,a literally does absolutely nothing but switch which name refers to which value.

[todd_dsm]

@murgatroid99 I'm running at I've shared it: copy it out, paste it into a file called swap2vars.py, change x and y to whatever you want and run it. On my Mac and Linux machines both functions produce the same result: exponent notation in the case the word boundary is crossed.

[murgatroid99]

Yes, and swapNosL(1e10, 1e-10) outputs (0.0, 10000000000.0). 0!=1e-10, so that it different behavior, and incorrect.

[todd_dsm]

@murgatroid99 there is a process or environmental difference; that's the ONLY THING that could explain the difference in output. Not sure what you're doing and now I don't care. I get the same result in both.

[murgatroid99]

If you think it's the environment, we can use a web-based Python interpreter. We should definitely get the same result in that case. Here's an example: pythonfiddle.com/different-swap-functions.

[Brad Larson]

As a warning, attempting to insult others by referencing Autism spectrum disorders will not be tolerated here. I've edited the responsible comments to remove these references.

[todd_dsm]

Actually, you're right. At the time my friend could not remember what it was. She could remember the problem but not the name of the solution. I stumbled across XOR recently and ask her about it; she confirmed.

[todd_dsm]

Actually, my hopes with initial share were intended to be a building block to a larger conversation terminating with a language-agnostic answer; those hopes died almost immediately. My example just happened to be in python. That's just where I was at the time. As far as I'm concerned @afeldspar provided the right answer.

[Gokul Kurup]

x = 15 y =5 ; x = 15 + 5 =20 ; y =20-15 = 5; y value is 5 now. x = 20-5 =15;

[Peter Mortensen]

Wikipedia: XOR swap algorithm