Почему это невозможно? Если у вас есть журнал удаленных пакетов, просто запустите
sudo apt-get install package1 package2 package3 ...
Это должно действительно сделать трюк. Если у вас возникли проблемы, отправьте свой dpkg.log и любые ошибки / проблемы, с которыми вы столкнулись здесь.
P.S. Опция --purge просто гарантирует, что все файлы конфигурации также будут удалены.